เครื่องคำนวณเมทริกซ์ประชิด

แปลงระหว่างเมทริกซ์ประชิด, รายการขอบ และรายการประชิด ตรวจสอบกราฟระบุทิศทาง/ไม่ระบุทิศทางอัตโนมัติ คำนวณลำดับดีกรี, ความหนาแน่น, ส่วนประกอบที่เชื่อมกัน และกำลังของเมทริกซ์ — พร้อมการแสดงภาพกราฟ SVG แบบโต้ตอบ

ตัวอย่างด่วน:

สามเหลี่ยมพร้อมหาง (ไม่ระบุทิศทาง) วงจร (ระบุทิศทาง) K4 (รายการประชิด) เมทริกซ์ 4×4 ป้ายกำกับตัวเลข

↔ รายการขอบ ☰ รายการประชิด ▦ เมทริกซ์ประชิด

ข้อมูลกราฟ

รองรับ A-B, A->B, A B, A,B หรือแถวเมทริกซ์เช่น 0 1 1 0 ใช้ตัวอักษร ตัวเลข หรือขีดล่างสำหรับป้ายกำกับจุดยอด

ป้ายกำกับเมทริกซ์ (ไม่บังคับ)

ป้ายกำกับคั่นด้วยจุลภาคหรือช่องว่าง หนึ่งชื่อต่อหนึ่งแถวเมทริกซ์ หากเว้นไว้จะใช้ค่าเริ่มต้นเป็น A, B, C…

ประเภทกราฟ

Embed เครื่องคำนวณเมทริกซ์ประชิด Widget

เกี่ยวกับ เครื่องคำนวณเมทริกซ์ประชิด

เครื่องคำนวณเมทริกซ์ประชิด เป็นเครื่องมือทางทฤษฎีกราฟที่แปลงระหว่างรูปแบบการแทนกราฟมาตรฐานสามรูปแบบ ได้แก่ เมทริกซ์ประชิด, รายการขอบ และ รายการประชิด พร้อมทั้งเสริมผลลัพธ์ด้วยการวิเคราะห์โครงสร้าง: ลำดับดีกรี, ความหนาแน่นของกราฟ, ส่วนประกอบที่เชื่อมโยง และการยกกำลังเมทริกซ์ ระบบจะตรวจจับโดยอัตโนมัติว่าอินพุตของคุณเป็นกราฟแบบระบุทิศทางหรือไม่ระบุทิศทาง และแสดงผลภาพ SVG แบบสดไปพร้อมกับผลลัพธ์ทุกครั้ง

เมทริกซ์ประชิดคืออะไร?

สำหรับกราฟ G = (V, E) ที่มีจุดยอด n จุด เมทริกซ์ประชิด ของกราฟคือเมทริกซ์จัตุรัสขนาด n × n ชื่อ A ซึ่งสมาชิก A[i][j] มีค่าเป็น 1 หากมีขอบจากจุดยอด i ไปยังจุดยอด j และเป็น 0 ในกรณีอื่น

A[i][j] = 1 หาก (v_i, v_j) ∈ E , มิฉะนั้น 0

สำหรับกราฟไม่ระบุทิศทาง เมทริกซ์ประชิดจะ สมมาตร เสมอ: ทุกขอบ {u, v} จะส่งผลให้ทั้ง A[u][v] = 1 และ A[v][u] = 1 ส่วนกราฟระบุทิศทาง (digraph) เมทริกซ์อาจไม่สมมาตร ซึ่งสะท้อนถึงทิศทางของแต่ละส่วนโค้ง

การแสดงผลสามรูปแบบ — เลือกแบบที่เหมาะกับปัญหาของคุณ

รูปแบบ	พื้นที่ (Space)	การค้นหาขอบ	การแจกแจงเพื่อนบ้าน	เหมาะสำหรับ
เมทริกซ์ประชิด	Θ(n²)	O(1)	Θ(n)	กราฟหนาแน่น; พีชคณิตเมทริกซ์ (การยกกำลัง, ค่าเจาะจง)
รายการประชิด	Θ(n + m)	O(deg v)	Θ(deg v)	กราฟเบาบาง; อัลกอริทึม BFS/DFS และเส้นทางสั้นที่สุด
รายการขอบ	Θ(m)	Θ(m)	Θ(m)	อินพุต/เอาต์พุต, MST ของ Kruskal, อัลกอริทึมที่เน้นขอบเป็นหลัก

ตัวชี้วัดหลักที่คำนวณได้

ลำดับดีกรี

สำหรับกราฟไม่ระบุทิศทาง ดีกรี ของจุดยอดคือจำนวนขอบที่มาบรรจบกัน (โดยบ่วงนับเป็นสอง) สำหรับกราฟระบุทิศทาง แต่ละจุดยอดจะมี ดีกรีเข้า (ส่วนโค้งเข้า) และ ดีกรีออก (ส่วนโค้งออก) รายการดีกรีที่เรียงลำดับแล้วเป็นค่าคงตัวของกราฟแบบคลาสสิกที่ใช้ในการทดสอบสมสัณฐาน (Isomorphism) และทฤษฎีบท Erdős–Gallai

Handshaking Lemma: Σ deg(v) = 2m (ไม่ระบุทิศทาง) Σ in-deg(v) = Σ out-deg(v) = m (ระบุทิศทาง)

ความหนาแน่นของกราฟ

ความหนาแน่นวัดว่ากราฟนั้น "เต็ม" แค่ไหนเมื่อเทียบกับจำนวนขอบสูงสุดที่เป็นไปได้บนจุดยอด n จุด

ไม่ระบุทิศทาง: D = 2m / (n(n−1)) ระบุทิศทาง: D = m / (n(n−1))

ความหนาแน่น 0 หมายถึงไม่มีขอบเลย, 1 หมายถึงกราฟบริบูรณ์ และค่าที่ต่ำกว่า 0.1 มักบ่งบอกว่าเป็นกราฟเบาบางซึ่งรายการประชิดจะประหยัดพื้นที่มากกว่าเมทริกซ์

ส่วนประกอบที่เชื่อมโยง

ส่วนประกอบที่เชื่อมโยง คือเซตย่อยสูงสุดของจุดยอดที่ทุกคู่เชื่อมต่อกันด้วยทางเดิน สำหรับกราฟระบุทิศทาง เครื่องคำนวณนี้จะรายงาน ส่วนประกอบที่เชื่อมโยงอย่างอ่อน (โดยไม่สนใจทิศทางของลูกศร) — ซึ่งเป็นเซตย่อยเดียวกับที่คุณจะได้จากการถือว่าแต่ละส่วนโค้งเป็นขอบที่ไม่ระบุทิศทาง

การยกกำลังเมทริกซ์ (A², A³ ... )

ทฤษฎีบทพื้นฐานของทฤษฎีกราฟเชิงพีชคณิตระบุว่า สมาชิก (i, j) ของ A^k เท่ากับจำนวนทางเดินที่มีความยาว k พอดีจากจุดยอด i ไปยังจุดยอด j ดังนั้น:

A²[i][i] เท่ากับดีกรีของจุดยอด i (ในกราฟไม่ระบุทิศทาง) เนื่องจากทางเดิน 2 ขั้นจาก i กลับมาที่ตัวเองคือ "ไปหาเพื่อนบ้านแล้วกลับมา"
รอย (Trace) ของ A³ หารด้วย 6 คือจำนวนรูปสามเหลี่ยมในกราฟไม่ระบุทิศทาง
การที่ Aⁿ⁻¹ มีสมาชิกเป็นศูนย์หรือไม่ สามารถบอกได้ว่ากราฟนั้นเชื่อมโยงกันหรือไม่

รูปแบบอินพุตที่รองรับ

1. รายการขอบ

หนึ่งขอบต่อบรรทัดหรือคั่นด้วยจุลภาค สามารถใช้ตัวคั่นเหล่านี้ได้: A-B, A B, A,B, A->B, A--B ใช้ -> หากคุณต้องการบังคับให้เป็นการแปลความหมายแบบระบุทิศทาง

A-B, B-C, C-A, C-D (กราฟไม่ระบุทิศทาง วงจร 4 จุดพร้อมหาง) A->B, B->C, C->D, D->A (กราฟระบุทิศทาง วงจรยาว 4)

2. รายการประชิด

หนึ่งบรรทัดต่อจุดยอด ในรูปแบบ จุดยอด: เพื่อนบ้าน1, เพื่อนบ้าน2, ... ลำดับไม่มีความสำคัญ; จุดยอดที่หายไปจะถูกเพิ่มโดยอัตโนมัติจากรายการเพื่อนบ้าน

A: B, C, D B: A, C C: A, B, D D: A, C

3. เมทริกซ์ประชิด

หนึ่งแถวต่อบรรทัดด้วยค่า 0/1 ที่คั่นด้วยช่องว่างหรือจุลภาค เมทริกซ์ต้องเป็นจัตุรัส สามารถกำหนดป้ายกำกับเองได้ในช่องป้ายกำกับเมทริกซ์ (มิฉะนั้นจะใช้ A, B, C…)

0 1 1 0 1 0 1 1 1 1 0 1 0 1 1 0

วิธีใช้งานเครื่องคำนวณนี้

เลือกรูปแบบอินพุต โดยใช้แท็บตัวเลือก: รายการขอบ, รายการประชิด หรือเมทริกซ์ประชิด
วางหรือพิมพ์กราฟของคุณ ในพื้นที่ข้อความ สำหรับอินพุตเมทริกซ์ สามารถเพิ่มป้ายกำกับในช่องป้ายกำกับเมทริกซ์ได้
เลือกประเภทกราฟ — ปล่อยไว้ที่ ตรวจจับอัตโนมัติ แล้วเครื่องคำนวณจะอนุมานทิศทางจากลูกศร (->) หรือความสมมาตรของเมทริกซ์ หรือเลือกแบบระบุทิศทางหรือระบุทิศทางหากต้องการกำหนดเอง
คลิก แปลงและวิเคราะห์กราฟ หน้าผลลัพธ์จะแสดงเมทริกซ์ประชิด, ภาพ SVG แบบโต้ตอบ, รูปแบบข้อความอีกสองแบบ, สถิติดีกรี, ส่วนประกอบที่เชื่อมโยง และเมทริกซ์การยกกำลัง A² และ A³ เมื่อกราฟมีขนาดเล็กพอ
วางเมาส์เหนือแถวเมทริกซ์หรือจุดยอดในกราฟ เพื่อเน้นแถว/คอลัมน์และขอบที่เกี่ยวข้อง — ซึ่งเป็นเครื่องพิสูจน์ทันทีว่าแต่ละรูปแบบเข้ารหัสข้อมูลเดียวกัน

ตัวอย่างการใช้งาน

พิจารณากราฟไม่ระบุทิศทางบนจุดยอด {A, B, C, D} ที่มีขอบ AB, BC, CA, CD เมทริกซ์ประชิดคือ:

A B C D A [ 0 1 1 0 ] B [ 1 0 1 0 ] C [ 1 1 0 1 ] D [ 0 0 1 0 ]

ข้อเท็จจริงหลักที่เครื่องคำนวณประมวลผลได้:

สมมาตรหรือไม่? ใช่ — ยืนยันว่าเป็นแบบไม่ระบุทิศทาง
ลำดับดีกรี: (3, 2, 2, 1) — จุดยอด C เป็นศูนย์กลาง
ความหนาแน่น: 2·4 / (4·3) = 0.667 — กราฟที่มีความหนาแน่นปานกลาง
เชื่อมโยงหรือไม่? ใช่ เป็นส่วนประกอบเดียว
รูปสามเหลี่ยม: มีหนึ่งรูปพอดี (A–B–C) ตามที่ยืนยันโดย tr(A³) = 6

การประยุกต์ใช้งานทั่วไป

การวิเคราะห์เครือข่ายสังคม — กราฟความเป็นเพื่อน / ผู้ติดตาม, ความเป็นศูนย์กลาง
กราฟเว็บและอ้างอิง — PageRank และ HITS ทำงานโดยตรงบน A และ A^T
การหาเส้นทางและเครือข่าย — เส้นทางสั้นที่สุด, min-cut, max-flow
เคมี — กราฟโมเลกุลที่มีอะตอมเป็นจุดยอดและพันธะเป็นขอบ
การวางแผนงานและการจัดการความพึ่งพา — กราฟระบุทิศทางแบบไม่มีวัฏจักร (DAGs) ในระบบบิลด์
โซ่มาร์คอฟ — เมทริกซ์สโตแคสติกแบบแถวที่ได้จากกราฟจะเข้ารหัสความน่าจะเป็นของการเปลี่ยนสถานะ

คำถามที่พบบ่อย

เมทริกซ์ประชิดคืออะไร?

เมทริกซ์ประชิดคือเมทริกซ์จัตุรัสขนาด n × n ที่ใช้แทนกราฟจำกัด แต่ละเซลล์ A[i][j] จะเป็น 1 หากมีขอบจากจุดยอด i ไปยังจุดยอด j และเป็น 0 ในกรณีอื่น สำหรับกราฟไม่ระบุทิศทาง เมทริกซ์จะสมมาตร ดังนั้น A[i][j] = A[j][i] เมทริกซ์นี้ทำให้ตรวจสอบได้ง่ายว่าจุดยอดสองจุดเชื่อมต่อกันหรือไม่ในเวลาคงที่ และการยกกำลังเมทริกซ์จะเข้ารหัสจำนวนทางเดินระหว่างจุดยอด

จะทราบได้อย่างไรว่ากราฟเป็นแบบระบุทิศทางจากเมทริกซ์ประชิด?

หากเมทริกซ์ประชิดมีความสมมาตร หมายความว่า A[i][j] เท่ากับ A[j][i] สำหรับดัชนีทุกคู่ กราฟนั้นจะไม่ระบุทิศทาง หากมีอย่างน้อยหนึ่งคู่ที่ A[i][j] แตกต่างจาก A[j][i] กราฟนั้นจะเป็นแบบระบุทิศทาง เครื่องคำนวณนี้จะตรวจสอบความสมมาตรโดยอัตโนมัติเมื่อคุณเลือกตัวเลือกตรวจจับอัตโนมัติ

กำลังที่ k ของเมทริกซ์ประชิดหมายถึงอะไร?

สมาชิก (i, j) ของ A^k นับจำนวนทางเดินที่มีความยาว k พอดีจากจุดยอด i ไปยังจุดยอด j ตัวอย่างเช่น A²[i][j] คือจำนวนเส้นทาง 2 ขั้นตอน ซึ่งเท่ากับจำนวนเพื่อนบ้านร่วมกันระหว่าง i และ j ในกราฟไม่ระบุทิศทาง คุณสมบัตินี้ใช้ในอัลกอริทึมสำหรับการนับรูปสามเหลี่ยม, การเข้าถึงได้ และการคำนวณแบบ PageRank

ความหนาแน่นของกราฟคืออะไร?

ความหนาแน่นของกราฟคืออัตราส่วนของจำนวนขอบที่มีอยู่ต่อจำนวนขอบสูงสุดที่เป็นไปได้ สำหรับกราฟอย่างง่ายแบบไม่ระบุทิศทางที่มีจุดยอด n จุด ความหนาแน่น = 2m / (n(n-1)) สำหรับกราฟระบุทิศทาง ความหนาแน่น = m / (n(n-1)) ความหนาแน่นใกล้ 0 หมายถึงกราฟเบาบาง ความหนาแน่นเป็น 1 หมายถึงกราฟบริบูรณ์

เมทริกซ์ประชิดแตกต่างจากรายการประชิดอย่างไร?

เมทริกซ์ประชิดจะเก็บการเชื่อมต่อสำหรับจุดยอดทุกคู่โดยใช้บิตขนาด n² ทำให้การค้นหาเพื่อนบ้านเป็น O(1) แต่การใช้หน่วยความจำเป็น O(n²) รายการประชิดจะเก็บเฉพาะเพื่อนบ้านจริงของแต่ละจุดยอดเท่านั้น ทำให้ใช้หน่วยความจำ O(n + m) ซึ่งเล็กกว่ามากสำหรับกราฟเบาบาง แต่การค้นหาเพื่อนบ้านต้องใช้การสแกนเชิงเส้น เมทริกซ์ดีกว่าสำหรับกราฟหนาแน่นและการดำเนินการพีชคณิตเมทริกซ์ รายการดีกว่าสำหรับกราฟเบาบางและอัลกอริทึมการท่องกราฟ เช่น BFS/DFS

เครื่องมือนี้สามารถจัดการกราฟแบบถ่วงน้ำหนักได้หรือไม่?

เครื่องคำนวณปัจจุบันเน้นที่เมทริกซ์ประชิดแบบไม่ถ่วงน้ำหนักที่มีค่า 0/1 หากคุณวางเมทริกซ์ที่มีน้ำหนักเป็นตัวเลขที่ไม่ใช่ศูนย์ ทุกเซลล์ที่ไม่ใช่ศูนย์จะถูกประมวลผลเสมือนเป็น 1 สำหรับการวิเคราะห์โครงสร้าง สำหรับการคำนวณกราฟถ่วงน้ำหนัก เช่น เส้นทางสั้นที่สุด โปรดพิจารณาใช้เครื่องมือกราฟถ่วงน้ำหนักโดยเฉพาะ