แบบจำลองทางคณิตศาสตร์. ลักษณะเมตริกของกราฟที่ไม่มีทิศทาง

คำแถลง. หากมีเส้นทางสำหรับจุดยอดสองจุดเชื่อมต่อกัน จะต้องมีเส้นทางขั้นต่ำที่เชื่อมต่อจุดยอดเหล่านี้ แทนความยาวของเส้นทางนี้เป็นง(โวลต์ว).

คำนิยาม. มูลค่าง(โวลต์w) (จำกัด หรือ ไม่มีที่สิ้นสุด) จะถูกเรียก ระยะห่างระหว่างจุดยอด โวลต์ ว . ระยะทางนี้เป็นไปตามสัจพจน์ของเมตริก:

1) ง(โวลต์ว) 0 และง(โวลต์w) = 0 ก็ต่อเมื่อวี=ว;

2) d(v, w) = d(w, v);

3) d(v, w) d(v, u) + d(u, w).

คำนิยาม. เส้นผ่านศูนย์กลางของกราฟที่เชื่อมต่อคือระยะทางที่เป็นไปได้สูงสุดระหว่างจุดยอดสองจุด

คำนิยาม. ศูนย์กลางกราฟเป็นจุดยอดเช่นนั้น ระยะทางสูงสุดระหว่างมันกับจุดสูงสุดอื่น ๆ นั้นเล็กที่สุดเท่าที่จะทำได้ ระยะทางนี้เรียกว่า รัศมีกราฟ.

ตัวอย่าง 82.

สำหรับกราฟ G แสดงในรูป 3.16 จงหารัศมี เส้นผ่านศูนย์กลางและศูนย์กลาง

ข้าว. 3.16. นับเช่น 82

วิธีการแก้.

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

การใช้เมทริกซ์ผลลัพธ์สำหรับแต่ละจุดยอดของกราฟ ชกำหนดการลบที่ใหญ่ที่สุดออกจากนิพจน์: สำหรับ ผม,เจ = 1, 2, …, 5. เป็นผลให้เราได้รับ: r(v1) = 3,r(v2) = 2,r(v3) = 2,r(v4) = 2,r(v5) = 3.ค่าต่ำสุดของตัวเลขที่ได้คือรัศมีของกราฟ ชสูงสุดคือเส้นผ่านศูนย์กลางของกราฟ ช. วิธี, อาร์(ช) = 2และ ง(ช) = 3, ศูนย์กลางคือจุดยอด วี 2 ,วี 3 ,v 4.

การคำนวณระยะทางและการกำหนดเส้นทางในกราฟเป็นหนึ่งในปัญหาที่ชัดเจนและใช้งานได้จริงซึ่งเกิดขึ้นในทฤษฎีกราฟ ให้เราแนะนำคำจำกัดความที่จำเป็นบางประการ

ความเยื้องศูนย์กลางจุดยอดของกราฟ - ระยะทางไปยังจุดยอดที่อยู่ห่างจากจุดยอดมากที่สุด สำหรับกราฟที่ไม่ได้กำหนดไว้ น้ำหนัก ขอบของมัน ระยะทางถูกกำหนดเป็นจำนวนของขอบ

รัศมีกราฟคือความเยื้องศูนย์ต่ำสุดของจุดยอด และ เส้นผ่านศูนย์กลาง กราฟคือความเยื้องศูนย์กลางสูงสุดของจุดยอด

ศูนย์กลางจุดยอดในรูปแบบกราฟที่มีความเยื้องศูนย์ เท่ากับรัศมี. จุดกึ่งกลางของกราฟอาจประกอบด้วยจุดยอดของกราฟหนึ่งจุด หลายจุดหรือทั้งหมด

อุปกรณ์ต่อพ่วงจุดยอดมีความเยื้องศูนย์เท่ากับเส้นผ่านศูนย์กลาง

เรียกว่าโซ่ธรรมดาที่มีความยาวเท่ากับเส้นผ่านศูนย์กลางของกราฟ เส้นผ่านศูนย์กลาง .

ทฤษฎีบท 12.1ในกราฟที่เชื่อมต่อกัน เส้นผ่านศูนย์กลางจะอยู่ในอันดับสูงสุดของเมทริกซ์ที่อยู่ติดกัน

ทฤษฎีบท 12.2(จอร์แดน) ต้นไม้ทุกต้นมีจุดศูนย์กลางที่ประกอบด้วยจุดยอดที่อยู่ติดกันหนึ่งหรือสองจุด

ทฤษฎีบท 12.3ถ้าเส้นผ่านศูนย์กลางของต้นไม้เป็นเลขคู่ แสดงว่าต้นไม้มีจุดศูนย์กลางจุดเดียว และโซ่เส้นผ่านศูนย์กลางทั้งหมดพาดผ่าน ถ้าเส้นผ่านศูนย์กลางเป็นเลขคี่ แสดงว่ามีศูนย์กลางสองจุด และโซ่เส้นผ่านศูนย์กลางทั้งหมดมีขอบเชื่อมต่อกัน

อย่างชัดเจน ค่าปฏิบัติศูนย์กลางของกราฟ ตัวอย่างเช่น ถ้า เรากำลังพูดถึงเกี่ยวกับกราฟถนนที่มีจุดยอดเมืองจากนั้นแนะนำให้วางในศูนย์คณิตศาสตร์ ศูนย์บริหาร,โกดังเก็บสินค้า ฯลฯ วิธีการเดียวกันนี้สามารถใช้กับกราฟถ่วงน้ำหนัก โดยที่ระยะทางคือน้ำหนักของขอบ ในฐานะน้ำหนัก คุณสามารถใช้ระยะทางแบบยุคลิด เวลา หรือค่าใช้จ่ายในการเคลื่อนที่ระหว่างจุดต่างๆ

ตัวอย่าง 12.5ค้นหารัศมี เส้นผ่านศูนย์กลางและจุดศูนย์กลางของกราฟที่แสดงในรูป 12.1.

วิธีการแก้.ในปัญหานี้สะดวกในการใช้งาน เมทริกซ์ระยะทาง S. องค์ประกอบของเมทริกซ์สมมาตรกำลังสองนี้เท่ากับระยะห่างระหว่างจุดยอด ผมและด้านบน เจ. สำหรับกราฟที่แสดงในรูป 12.1 เมทริกซ์ระยะทางมี มุมมองถัดไป:

. (12.2)

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

№

รัศมีกราฟ รคือความเยื้องศูนย์ต่ำสุดของจุดยอด ที่ กรณีนี้ ร= 2 จุดยอดหมายเลข 2 หมายเลข 4 และหมายเลข 5 มีความเยื้องศูนย์ จุดเหล่านี้เป็นจุดศูนย์กลางของกราฟ เส้นผ่านศูนย์กลางของกราฟ งคือความเยื้องศูนย์กลางสูงสุดของจุดยอด ในกรณีนี้ ง= 3. จุดยอดหมายเลข 1 และหมายเลข 3 มีความเยื้องศูนย์ นี่คือขอบของกราฟ ในกราฟที่ศึกษา จุดยอดกลายเป็นจุดกึ่งกลางหรือส่วนปลาย มีจุดยอดอื่นๆ ในกราฟที่มีลำดับสูงกว่า

ความเยื้องศูนย์ของจุดยอดของกราฟขนาดเล็กสามารถคำนวณได้ง่ายโดยการคำนวณโดยตรงจากรูป อย่างไรก็ตาม กราฟไม่ได้ถูกกำหนดโดยการวาดเสมอไป นอกจากนี้กราฟอาจมี ขนาดใหญ่. ดังนั้นจึงจำเป็นต้องมีวิธีอื่นในการแก้ปัญหาก่อนหน้านี้ ทราบทฤษฎีบทต่อไปนี้

ทฤษฎีบท 12.4 อนุญาต เป็นเมทริกซ์คำคุณศัพท์ของกราฟ G โดยไม่มีลูป และ ที่ไหน จากนั้นจะเท่ากับจำนวนเส้นทางของความยาว k จากจุดยอดถึงจุดยอด

การแก้ปัญหาของทฤษฎีกราฟโดยใช้การแปลงต่างๆ ของเมทริกซ์ adjacency เรียกว่า วิธีพีชคณิต .

ตัวอย่าง 12.6ค้นหาเมทริกซ์ระยะทางของกราฟที่แสดงในรูป 12.1 โดยวิธีพีชคณิต

วิธีการแก้.เมทริกซ์คำคุณศัพท์ของกราฟนี้คือ:

.

เราจะเติมเมทริกซ์ระยะทางโดยพิจารณาจากองศาของเมทริกซ์ประชิด หน่วยเมทริกซ์ที่อยู่ติดกันแสดงคู่ของจุดยอดที่มีระยะห่างระหว่างกัน 1 จุด (นั่นคือเชื่อมต่อกันด้วยขอบเส้นเดียว)

.

องค์ประกอบในแนวทแยงของเมทริกซ์ระยะทางเป็นศูนย์ คูณเมทริกซ์คำคุณศัพท์ด้วยตัวเอง:

.

ตามทฤษฎีบทระหว่างจุดยอด 2 และ 3, 1 และ 4 เป็นต้น มีบางเส้นทางที่มีความยาว 2 (เนื่องจากดีกรีของเมทริกซ์คือ 2) ที่นี่ไม่ได้ใช้จำนวนเส้นทางความจริงของการมีอยู่ของเส้นทางและความยาวของเส้นทางมีความสำคัญซึ่งระบุด้วยองค์ประกอบที่ไม่ใช่ศูนย์ของระดับของเมทริกซ์ซึ่งไม่ตรงกับองค์ประกอบที่ระบุไว้เมื่อคำนวณ เส้นทางที่มีความยาวน้อยกว่า เราใส่ 2 ในองค์ประกอบว่างของเมทริกซ์ระยะทางและรับ ประมาณถัดไป:

.

ยังไม่ทราบระยะห่างระหว่างจุดยอด 1 และ 3 เราจะคูณเมทริกซ์ประชิด ในตัวเองจนถึงเมทริกซ์ องค์ประกอบที่ไม่เป็นโมฆะจะไม่ปรากฏขึ้น . จากนั้นองค์ประกอบที่สอดคล้องกันของเมทริกซ์ระยะทาง เท่ากับปริญญาเมทริกซ์ที่อยู่ติดกัน: . ในขั้นตอนต่อไปเราจะได้รับ

ในส่วนสุดท้าย เราได้เน้นย้ำว่าเมทริกซ์คำเชื่อม $A$ ที่แนะนำในที่นี้ หรือเมทริกซ์คำเชื่อมจุดยอดของกราฟ มีบทบาทสำคัญมาก บทบาทสำคัญในทฤษฎีกราฟ เราสังเกตว่าเป็นข้อดีของเมทริกซ์นี้ - มันเป็นกำลังสองของลำดับ เท่ากับจำนวนแถวของเมทริกซ์อุบัติการณ์ $B$ ซึ่งก็คือตามกฎแล้วประกอบด้วย จำนวนน้อยกว่าองค์ประกอบ ประการที่สอง เมทริกซ์นี้เก็บข้อมูลทั้งหมดเกี่ยวกับขอบของกราฟ และสำหรับจำนวนจุดยอดที่กำหนด จะอธิบายกราฟโดยไม่ซ้ำกัน เมทริกซ์คำคุณศัพท์ เช่น เมทริกซ์อุบัติการณ์ของกราฟ คือเมทริกซ์ (0,1) เช่น องค์ประกอบของมันสามารถพิจารณาได้ว่าเป็นองค์ประกอบของโครงสร้างพีชคณิตอื่นๆ และไม่เพียงแต่เป็นองค์ประกอบของเซตของจำนวนเต็มเท่านั้น โดยเฉพาะอย่างยิ่ง เราสังเกตว่าองค์ประกอบของเมทริกซ์คำคุณศัพท์สามารถพิจารณาได้ว่าเป็นองค์ประกอบของพีชคณิตบูลีน ซึ่งอยู่ภายใต้กฎของเลขคณิตบูลีน แต่ไม่ได้อธิบายสิ่งนี้อย่างถูกต้อง ก่อนที่จะเติมช่องว่างนี้ เราเน้นย้ำถึงข้อดีของเมทริกซ์คำเชื่อม ซึ่งตามมาจากความเป็นสี่เหลี่ยมจัตุรัส

ในการทำเช่นนี้ เราระลึกถึงกฎสำหรับการคูณเมทริกซ์ ให้กำหนดเมทริกซ์ที่มีองค์ประกอบเป็นตัวเลข: เมทริกซ์ $A$ ของมิติ $n\times m$ กับองค์ประกอบ $a_(ik)$ และเมทริกซ์ $B$ ของมิติ $m\times q$ กับองค์ประกอบ $b_(kj)$ . เมทริกซ์ $C$ ของมิติ $n\times q$ เรียกว่าผลคูณของเมทริกซ์ $A$ และ $B$ (ลำดับเป็นสิ่งสำคัญ) ถ้าองค์ประกอบ $c_(ij)$ ถูกกำหนดดังนี้: $c_(ij) = \sum\limits_( k = 1)^m (a_(ik) b_(kj))$ ผลคูณของเมทริกซ์เขียนด้วยวิธีปกติ $AB=C$ อย่างที่คุณเห็น ผลคูณของเมทริกซ์ต้องการความสม่ำเสมอในขนาดของปัจจัยที่หนึ่งและสอง (จำนวนคอลัมน์ของเมทริกซ์ปัจจัยแรกเท่ากับจำนวนแถวของเมทริกซ์ปัจจัยที่สอง) ข้อกำหนดนี้จะหายไปหากเราพิจารณาเมทริกซ์กำลังสองที่มีลำดับเดียวกัน ดังนั้น เราสามารถพิจารณากำลังพลของเมทริกซ์กำลังสองได้ นี่คือประโยชน์อย่างหนึ่ง เมทริกซ์สี่เหลี่ยมด้านหน้าของสี่เหลี่ยม ข้อดีอีกประการหนึ่งคือเราสามารถตีความกราฟให้กับองค์ประกอบระดับของเมทริกซ์คำคุณศัพท์

ให้เมทริกซ์คำคุณศัพท์ $A$ อยู่ในรูปแบบ: $A = \left(((\begin(array)(*c) (a_(11) ) & (a_(12) ) & (...) & ( a_(1n ) ) \\ (a_(21) ) & (a_(22) ) & (...) & (a_(2n) ) \\ (...) & (...) & (.. .) & (...) \\ (a_(n1) ) & (a_(n2) ) & (...) & (a_(nn) ) \\ \end(อาร์เรย์) )) \right)$, และกำลัง $k$th — $A^k = \left(((\begin(array)(*c) (a_(11)^((k)) ) & (a_(12)^((k)) ) ) & (...) & (a_(1n)^((k)) ) \\ (a_(21)^((k)) ) & (a_(22)^((k)) ) & ( .. .) & (a_(2n)^((k)) ) \\ (...) & (...) & (...) & (...) \\ (a_(n1)^ (( k)) ) & (a_(n2)^((k)) ) & (...) & (a_(nn)^((k)) ) \\ \end(อาร์เรย์) )) \right) $ โดยที่ $k = 2,3,...$ เห็นได้ชัดว่า $A^k$ เช่นเดียวกับเมทริกซ์ $A$ จะเป็นเมทริกซ์สมมาตร

ให้ $k=2$ จากนั้น $a_(ij)^(2)) = \sum\limits_(k = 1)^n (a_(il) a_(lj))$ ($i,j = 1,2,...,n $) และแต่ละเทอม $a_(il) a_(lj)$ เท่ากับ $0$ หรือ $1$ กรณีที่ $a_(il) a_(lj) = 1$ หมายความว่ามีขอบสองเส้นในกราฟ: ขอบ $\(i,l\)$ (เนื่องจาก $a_(il) = 1)$ และขอบ $\( l,j\)$ (ตั้งแต่ $a_(lj) = 1$) และด้วยเหตุนี้เส้นทาง $\(( \(i,l\), \(l,j\) )\)$ จาก $i จุดยอด $-th ถึง $j$-th ของความยาวสอง (เส้นทางของสองขอบ) ในที่นี้เรากำลังพูดถึงเส้นทาง ไม่ใช่ห่วงโซ่ เนื่องจากมีการระบุทิศทาง - จากจุดยอด $i$-th ไปยังจุดยอด $j$-th ดังนั้น $a_(ij)^(2))$ ให้จำนวนเส้นทางทั้งหมดบนกราฟ (ในการตีความทางเรขาคณิตของกราฟ) ที่มีความยาว 2 จากจุดยอด $i$th ถึง $j$th หนึ่ง.

ถ้า $k=3$ ดังนั้น $A^3 = A^2A = AA^2 = AAA$ และ $a_(ij)^((3)) = \sum\limits_(l_1 = 1)^n (a_( il_1 ) ) a_(l_1 j)^((2)) = $ $\sum\limits_(l_1 = 1)^n (a_(il_1 ) ) \left((\sum\limits_(l_2 = 1)^n ( a_ (l_1 l_2 ) a_(l_2 j) ) ) \right) =$ $\sum\limits_(l_1 = 1)^n (\sum\limits_(l_2 = 1)^n (a_(il_1 ) ) ) a_( l_1 l_2 ) a_(l_2 j) = \sum\limits_(l_1 ,l_2 = 1)^n (a_(il_1 ) a_(l_1 l_2 ) a_(l_2 j) )$

คำว่า $a_(il_1 ) a_(l_1 l_2 ) a_(l_2 j) $ ถ้ามีค่าเท่ากับ 1 จะกำหนดพาธที่มีความยาว 3 จากจุดยอด $i$-th ไปยังจุดยอด $j$-th และ ผ่านจุดยอด $l_1$ และ $l_2$ จากนั้น $a_(ij)^(3))$ จะแสดงจำนวนพาธที่มีความยาว 3 ซึ่งเชื่อมต่อจุดยอด $i$th และ $j$th ที่ กรณีทั่วไป$a_(ij)^((k))$ ระบุจำนวนพาธที่มีความยาว $k$ เชื่อมต่อจุดยอด $i$th และ $j$th นอกจากนี้ $a_(ij)^(k)) = \sum\limits_(l_1 ,l_2 ,...,l_(k - 1) = 1)^n (a_(il_1 ) a_(l_1 l_2 ) .. .) a_(l_(k - 2) l_(k - 1) ) a_(l_(k - 1) j)$.

เป็นที่ชัดเจนว่าปริมาณ $a_(ii)^((k)) $ ให้จำนวนเส้นทางปิดของความยาว $k$ เริ่มต้นและสิ้นสุดที่จุดยอด $i$ ดังนั้น เส้นทางที่มีความยาว 2 $a_(il) a_(li)$ หมายถึง เส้นทางที่ผ่านขอบ $\( i,l \)$ จากจุดยอด $i$ ไปยังจุดยอด $l$ และย้อนกลับ ดังนั้น $a_(ii)^(2)) = s_i$ นั่นคือ องค์ประกอบแนวทแยงของเมทริกซ์ $A^2$ เท่ากับกำลังของจุดยอดที่สอดคล้องกัน

ลองพิจารณาตอนนี้ ร่วมกับเมทริกซ์ $A$ เมทริกซ์ $\dot (A)$ ซึ่งแตกต่างจากเมทริกซ์ $A$ ตรงที่องค์ประกอบ (ตัวเลข 0 หรือ 1) ถือเป็นองค์ประกอบของพีชคณิตบูลีน ดังนั้นการดำเนินการกับเมทริกซ์ดังกล่าวจะดำเนินการตามกฎของพีชคณิตบูลีน เนื่องจากการดำเนินการของการบวกและการคูณเมทริกซ์ด้วยองค์ประกอบบูลีนจะลดลงเป็นการดำเนินการของการบวกและการคูณองค์ประกอบของเมทริกซ์เหล่านี้ตามกฎของเลขคณิตบูลีน เราหวังว่าสิ่งนี้จะไม่นำไปสู่ความยุ่งยาก เมทริกซ์ที่มีองค์ประกอบบูลีนจะเรียกว่าเมทริกซ์บูลีน เห็นได้ชัดว่าการดำเนินการของการบวกและการคูณของเมทริกซ์บูลีนถูกปิดในชุดของเมทริกซ์บูลีน เช่น ผลลัพธ์ของการดำเนินการเหล่านี้จะเป็นเมทริกซ์บูลีนอีกครั้ง

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

ผลลัพธ์ของการเพิ่มเมทริกซ์สมมาตรบูลีนสองตัวที่มีลำดับเดียวกันจะเป็นเมทริกซ์สมมาตรบูลีนที่มีลำดับเดียวกันโดยมีศูนย์ในตำแหน่งที่ทั้งสองเทอมมีศูนย์และเมทริกซ์ในที่เหล่านั้นซึ่งมีอย่างน้อยหนึ่งเทอมมีหน่วย ในการตีความกราฟ การดำเนินการนี้เรียกว่าการดำเนินการ การเพิ่มกราฟ. ผลรวมของสองกราฟ, ที่กำหนดบนจุดยอดชุดเดียวกันที่มีหมายเลขเดียวกัน เรียกว่ากราฟซึ่งจุดยอด i และ j ไม่ติดกัน หากไม่ติดกันสำหรับกราฟผลบวกทั้งสอง และจุด i และ j อยู่ติดกัน หากพวกมันอยู่ติดกันเป็นเวลาอย่างน้อย หนึ่งกราฟสรุป.

ให้เราตีความกำลังสองของเมทริกซ์บูลีน adjacency $\dot (A)^2$ กับค่า $\dot (a)_(ij)^((2)) = \sum\limits_(l = 1)^ n (\dot ( ก)_(อิล) \dot (a)_(lj) )$ เป็นที่ชัดเจนว่า $\dot (a)_(ij)^(2)) = 1$ ถ้าอย่างน้อยหนึ่งเทอม $\dot (a)_(il) \dot (a)_(lj) $ เท่ากัน ถึง 1 และ $\dot (a)_(ij)^(2)) = 0$ ถ้าพจน์ทั้งหมดเท่ากับ 0 ถ้าเมทริกซ์ $\dot (A)$ เป็นเมทริกซ์คำคุณศัพท์ของกราฟบางกราฟ เช่น เป็นเมทริกซ์สมมาตร (0,1) ที่มีเส้นทแยงมุมหลักเป็นศูนย์ ดังนั้นเมทริกซ์ $\dot (A)^2$ โดยทั่วไปจึงไม่ใช่เมทริกซ์ประชิดของกราฟตามความหมายที่เรานำมาใช้ เนื่องจากทั้งหมด องค์ประกอบในแนวทแยงมีค่าเท่ากับ 1 (หากกราฟไม่มีจุดยอดเดี่ยว) เพื่อที่จะมองว่าเมทริกซ์ดังกล่าวเป็นเมทริกซ์เชิงประชิด เมื่อพิจารณาการเชื่อมต่อระหว่างจุดยอดของระบบที่เชื่อมต่อซึ่งกำหนดให้ระบบนี้เป็นกราฟ เมื่อพิจารณาการเชื่อมต่อของจุดยอดกับตัวมันเอง เรียกว่า "ขอบ" ที่กำหนดการเชื่อมต่อของจุดสุดยอดกับตัวเอง ห่วง. เราจะดำเนินการต่อเช่นเดิมโดยใช้คำว่า กราฟ เราจะเข้าใจกราฟที่ไม่มีลูปและเกี่ยวกับกราฟที่มีการวนซ้ำหากไม่ชัดเจนจากบริบทเราจะพูดอย่างนั้น - กราฟที่มีการวนซ้ำ

พิจารณาผลรวม $\dot (A)^() = \dot (A) + \dot (A)^2$ เมทริกซ์ $\dot (A)^()$ ทำให้เราได้กราฟจากกราฟต้นฉบับโดยการ "อิ่มตัว" ด้วยการเชื่อมต่อเพิ่มเติมที่สอดคล้องกับเส้นทางของความยาว 2 นั่นคือจุดยอด $i$ และ $j$ อยู่ติดกัน ในกราฟใหม่ ถ้าพวกมันอยู่ติดกันในกราฟเดิม หรือจุดยอดเหล่านี้เชื่อมกันด้วยเส้นทางบางเส้นของความยาว 2 และจุด $i$ และ $j$ จะไม่อยู่ติดกัน ถ้าพวกมันไม่ติดกันในกราฟเดิม และมี ไม่มีเส้นทางที่มีความยาว 2 เชื่อมต่อจุดยอดเหล่านี้

$\dot (A)^() = \dot (A) + \dot (A)^2 + \dot (A)^3$ ถูกกำหนดในทำนองเดียวกัน นั่นคือในกราฟ กำหนดโดยเมทริกซ์$\dot (A)^()$ จุดยอด $i$ และ $j$ อยู่ติดกัน ถ้าพวกมันอยู่ติดกันในกราฟ $\dot (A)^()$ หรือจุดยอดเหล่านี้เชื่อมกันด้วยเส้นทางบางเส้นที่มีความยาว 3 ใน กราฟเดิม และจุดยอด $i$ และ $j$ จะไม่อยู่ติดกัน หากไม่ติดกันในกราฟ $\dot (A)^()$ และไม่มีเส้นทางที่มีความยาว 3 เชื่อมต่อจุดยอดเหล่านี้ในกราฟเดิม . และอื่น ๆ

โดยทั่วไป $\dot (A)^([k]) = \sum\limits_(i = 1)^k (\dot (A)^i) $ ง่ายต่อการดูว่า $\dot (A)^([k])$ ทั้งหมดสำหรับ $k \ge n - 1$ โดยที่ $n$ เป็นลำดับของเมทริกซ์ $\dot (A)$ มีค่าเท่ากัน . แท้จริงแล้ว ถ้าจุดยอด $i$ และ $j$ เชื่อมต่อกัน แสดงว่ามีเส้นทาง (ลูกโซ่) เชื่อมต่อจุดยอดเหล่านี้ ดังนั้นจึงมีเส้นทางธรรมดา (ลูกโซ่ธรรมดา) เชื่อมต่อจุดยอดเหล่านี้ เส้นทางอย่างง่ายที่เป็นไปได้สูงสุดในกราฟ $n$-vertex มีความยาว $n-1$ (เส้นทางอย่างง่ายที่เชื่อมต่อจุดยอดที่แตกต่างกันทั้งหมดของกราฟ) ดังนั้น ถ้าในเมทริกซ์ $\dot (A)^()$ มี 1 อยู่ในตำแหน่ง $(i,j)$ ก็ให้อยู่ในตำแหน่งเดียวกันในเมทริกซ์ $\dot (A)^([k])$ สำหรับ $k \ge n - 1$ จะเป็น 1 เช่นกัน เนื่องจากเมทริกซ์ $\dot (A)^()$ ถูกรวมไว้เป็นคำบูลีนในนิยามของเมทริกซ์ $\dot (A)^([k] )$. ถ้าในเมทริกซ์ $\dot (A)^()$ มี 0 แทนที่จะเป็น $(i,j)$ แสดงว่าไม่มีห่วงโซ่อย่างง่ายในกราฟที่เชื่อมต่อ $i$-th กับ $j$- จุดยอด ดังนั้น จึงไม่มีห่วงโซ่ใดเชื่อมต่อจุดยอดเหล่านี้เลย ดังนั้น ในกรณีที่อยู่ระหว่างการพิจารณาและในเมทริกซ์ $\dot (A)^([k])$ สำหรับ $k \ge n - 1$ ตำแหน่ง ($i$,$j)$ จะเป็น 0 นี่ พิสูจน์การยืนยันของเราเกี่ยวกับความเท่าเทียมกันของเมทริกซ์ทั้งหมด $\dot (A)^([k])$ สำหรับ $k \ge n - 1$ กับเมทริกซ์ $\dot (A)^()$ และ ดังนั้น สำหรับแต่ละเมทริกซ์ อื่นๆ.

เรียกว่าเมทริกซ์ $\dot (A)^()$ เมทริกซ์ของการปิดสกรรมกริยาของเมทริกซ์$\dot (A)$ เช่นเดียวกับเมทริกซ์คำคุณศัพท์ของการปิดสกรรมกริยาของกราฟที่กำหนดโดยเมทริกซ์ $\dot (A)$ ค่อนข้างชัดเจนว่าเมทริกซ์ของการปิดสกรรมกริยาของกราฟที่เชื่อมต่อคือเมทริกซ์คำเชื่อม กราฟที่สมบูรณ์, เช่น. เมทริกซ์สี่เหลี่ยมที่ประกอบด้วยหนึ่งเท่านั้น การสังเกตนี้ยังช่วยให้เราทราบวิธีการกำหนดการเชื่อมต่อของกราฟ: กราฟเชื่อมต่อกันก็ต่อเมื่อเมทริกซ์ของการปิดสกรรมกริยาของเมทริกซ์ประชิดจะประกอบด้วยเมทริกซ์เดียว (มันจะเป็นเมทริกซ์ของกราฟที่สมบูรณ์).

เมทริกซ์การปิดสกรรมกริยายังทำให้สามารถแก้ปัญหาการแยกกราฟออกเป็นส่วนประกอบที่เชื่อมต่อกันได้

ให้เราแสดงให้เห็นว่าขั้นตอนการปิดสกรรมกริยาช่วยให้เราสร้างสิ่งที่เรียกว่า "เมทริกซ์ระยะทาง" ได้อย่างไร ในการทำเช่นนี้ เราจะกำหนดระยะห่างระหว่างจุดยอด $i$ และ $j$ ถ้าจุดยอด $i$ และ $j$ เชื่อมโยงกัน ดังนั้น ระยะทางระหว่างนั้นเราจะตั้งชื่อความยาวของเส้นทางง่าย ๆ ที่น้อยที่สุด (ตามจำนวนการเคลื่อนที่ของขอบ) ที่เชื่อมต่อจุดยอดเหล่านี้ ถ้าจุดยอด $i$ และ $j$ ถูกตัดการเชื่อมต่อ เราจะตั้งค่าระยะทางเท่ากับศูนย์ (ศูนย์เป็นนิเสธของบางเส้นทางที่เชื่อมต่อจุดยอดเหล่านี้) ด้วยนิยามของระยะทางนี้ ระยะห่างระหว่างจุดยอดและตัวมันเองจะเท่ากับ 2 (ความยาวของเส้นทางตามขอบและด้านหลัง) หากมีการวนซ้ำที่จุดยอด ระยะห่างระหว่างจุดสุดยอดกับตัวมันเองจะเท่ากับ 1

ในการสร้างเมทริกซ์ระยะทางสำหรับกราฟจุดยอด $n$ ด้วยเมทริกซ์ประชิด $A$ ซึ่งจะระบุระยะห่างระหว่างจุดยอดสองจุด เราแนะนำเมทริกซ์ $A^(\(k\)) = A^([ k]) - A^()$ โดยที่ $k = 2,3,...,n - 1$ และ $A^(\(1\)) = A^() = A$ การไม่มีจุดเหนือสัญกรณ์เมทริกซ์แสดงว่าเราถือว่าเมทริกซ์ $A^([k])$ ($k = 1,2,...,n - 1)$ เป็นเมทริกซ์เชิงตัวเลข (0,1) หาได้ตามธรรมชาติจากเมทริกซ์ $\dot (A)^([k])$ (ตอนนี้เราถือว่าองค์ประกอบบูลีน 0 และ 1 เป็นตัวเลข 0 และ 1) ตามมาจากวิธีการสร้างเมทริกซ์ $A^([k])$ ที่ $A^([k]) \ge A^()$ ($k = 2,3,...,n - 1$ ) และ ดังนั้น $A^(\(k\))$ ($k = 1,2,...,n - 1$) คือ (0,1)-เมทริกซ์ ยิ่งไปกว่านั้น เมทริกซ์ $A^(\(2\))$ มี 1 เฉพาะในตำแหน่งที่จุดยอดที่กำหนดโดยสถานที่นี้ (หมายเลขแถวและหมายเลขคอลัมน์) เชื่อมต่อกันด้วยเส้นทางที่มีความยาว 2 และไม่ได้เชื่อมต่อกันด้วยเส้นทางที่เล็กกว่า เส้นทาง. ในทำนองเดียวกัน $A^(\(3\))$ มี 1 เฉพาะที่จุดยอดที่กำหนดโดยสถานที่นี้เชื่อมต่อกันด้วยเส้นทางที่มีความยาวสามและไม่เชื่อมต่อด้วยเส้นทางที่มีความยาวน้อยกว่า และอื่นๆ ดังนั้น เมทริกซ์ $D = \sum\limits_(k = 1)^(n - 1) (k \cdot A^(\(k\)))$ จะเป็นเมทริกซ์ระยะทางที่ต้องการ องค์ประกอบ $d_(ij)$ ของเมทริกซ์นี้จะเท่ากับระยะห่างระหว่างจุดยอด $i$ และ $j$ ระยะห่างระหว่างจุดยอด $u$ และ $v$ จะแสดงเป็น $d(u,v)$

ความคิดเห็นผลรวมเฉพาะ $a_(il_1 ) a_(l_1 l_2 ) ...a_(l_(k - 2) l_(k - 1) ) a_(l_(k - 1) j) = 1$ องค์ประกอบ $a_(ij ) ^((k))$ $k$-th ของเมทริกซ์คำคุณศัพท์ $A^k$ ระบุเฉพาะ $(i,j)$-path $i\(i,l_1\)l_1 \(l_1 ,l_2 \ )l_2 ...l_(k - 2) \(l_(k - 2) ,l_(k - 1) \)l_(k - 1) \(l_(k - 1) ,j\)j$ จาก $ จุดยอด i$ -th ถึง $j$-th ลำดับของจุดยอดและขอบที่อยู่ติดกันซึ่งเชื่อมต่อกัน $i\(i,l_1 \)l_1 \(l_1 ,l_2 \)l_2 ...l_(k - 2) \(l_(k - 2) ,l_(k - 1) \ )l_(k - 1) \(l_(k - 1) ,j\)j$ เรียกอีกอย่างว่า $(i,j)$-เส้นทาง. เส้นทางแตกต่างจากห่วงโซ่ที่ประกอบด้วยขอบที่อยู่ติดกันที่แตกต่างกันเท่านั้น ซึ่งอนุญาตให้มีขอบเท่ากันในเส้นทางได้ เส้นทางอย่างง่ายประกอบด้วยจุดยอดและขอบต่างๆ ที่อยู่ติดกัน เช่น เกือบจะเหมือนกับโซ่ธรรมดา

ค่อนข้างชัดเจนว่าองค์ประกอบ $d_(ij) $ ของเมทริกซ์ระยะทางกำหนดความยาวของห่วงโซ่ขั้นต่ำที่เชื่อมต่อจุดยอด $i$-th กับ $j$-th

พิจารณาตัวอย่างกราฟที่ให้ไว้ในรูปที่ 1 และ 2 เมทริกซ์เชิงประชิดและเมทริกซ์ระยะทาง

รูปที่ 1 (กราฟ $\Gamma _1$ เมทริกซ์ประชิด $A_1$ เมทริกซ์ระยะทาง $D_1$)
$A_1 = \left(((\begin(อาร์เรย์)(*c) 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 & 1 & 1 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ \end(อาร์เรย์) )) \right), $
$D_1 = \left(((\begin(อาร์เรย์)(*c) 2 & 1 & 1 & 1 & 2 & 3 & 3 & 3 & 3 & 2 & 3 & 3 & 2 \\ 1 & 2 & 1 & 1 & 2 & 3 & 3 & 3 & 3 & 2 & 3 & 3 & 2 \\ 1 & 1 & 2 & 1 & 1 & 2 & 2 & 2 & 2 & 1 & 2 & 2 & 1 \\ 1 & 1 & 1 & 2 & 2 & 3 & 3 & 3 & 3 & 2 & 3 & 3 & 2 \\ 2 & 2 & 1 & 2 & 2 & 1 & 1 & 1 & 2 & 1 & 2 & 2 & 1 \\ 3 & 3 & 2 & 3 & 1 & 2 & 1 & 1 & 3 & 2 & 3 & 3 & 2 \\ 3 & 3 & 2 & 3 & 1 & 1 & 2 & 1 & 3 & 2 & 3 & 3 & 2 \\ 3 & 3 & 2 & 3 & 1 & 1 & 1 & 2 & 3 & 2 & 3 & 3 & 2 \\ 3 & 3 & 2 & 3 & 2 & 3 & 3 & 3 & 2 & 1 & 1 & 1 & 2 \\ 2 & 2 & 1 & 2 & 1 & 2 & 2 & 2 & 1 & 2 & 1 & 1 & 1 \\ 3 & 3 & 2 & 3 & 2 & 3 & 3 & 3 & 2 & 2 & 2 & 1 & 2 \\ 3 & 3 & 2 & 3 & 2 & 3 & 3 & 3 & 1 & 1 & 1 & 2 & 2 \\ 2 & 2 & 1 & 2 & 1 & 2 & 2 & 2 & 2 & 1 & 2 & 2 & 2 \\ \end(อาร์เรย์) )) \right) $

ข้าว. 2 (กราฟ $\Gamma _2$ เมทริกซ์ประชิด $A_2$ เมทริกซ์ระยะทาง $D_2$)
$A_2 = \left(((\begin(อาร์เรย์)(*c) 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 1 & 0 \ \ 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ \end(อาร์เรย์) )) \right)$,
$D_2 = \left(((\begin(อาร์เรย์)(*c) 2 & 1 & 2 & 3 & 4 & 5 & 6 & 4 & 4 & 5 \\ 1 & 2 & 1 & 2 & 3 & 4 & 5 & ​​3 & 3 & 4 \\ 2 & 1 & 2 & 1 & 2 & 3 & 4 & 2 & 2 & 3 \\ 3 & 2 & 1 & 2 & 1 & 2 & 3 & 1 & 1 & 2 \ \ 4 & 3 & 2 & 1 & 2 & 1 & 2 & 2 & 2 & 3 \\ 5 & 4 & 3 & 2 & 1 & 2 & 1 & 3 & 3 & 4 \\ 6 & 5 & 4 & 3 & 2 & 1 & 2 & 4 & 4 & 5 \\ 4 & 3 & 2 & 1 & 2 & 3 & 4 & 2 & 2 & 3 \\ 4 & 3 & 2 & 1 & 2 & 3 & 4 & 2 & 2 & 1 \\ 5 & 4 & 3 & 2 & 3 & 4 & 5 & 3 & 1 & 2 \\ \end(อาร์เรย์) )) \ขวา). $

จากเมทริกซ์ $D_1$ และ $D_2$ มันง่ายที่จะกำหนด เส้นผ่านศูนย์กลาง$d_1$ ของกราฟ $\Gamma _1$ และ $d_2$ ของกราฟ $\Gamma _2$ เป็นค่าสูงสุดขององค์ประกอบของเมทริกซ์เหล่านี้ ดังนั้น $d_1 = 3$ และ $d_2 = 6$

นอกจากเมทริกซ์ระยะทางแล้ว ทฤษฎีกราฟยังพิจารณาเมทริกซ์อื่นๆ ด้วย ซึ่งองค์ประกอบของเมทริกซ์จะพิจารณาจากความยาวของเส้นทาง ตัวอย่างเช่นเป็น เมทริกซ์การเคลื่อนที่. ที่ เมทริกซ์ทัวร์องค์ประกอบ $(i,j)$th เท่ากับความยาวเส้นทางที่ยาวที่สุด (โซ่ที่ยาวที่สุด) จากจุดยอด $i$-th ไปยังจุด $j$-th และหากไม่มีเส้นทางดังกล่าวเลย ตามนิยามของระยะทาง $(i ,j)$-th องค์ประกอบของเมทริกซ์การเดินทางถูกตั้งค่าเท่ากับศูนย์ .

ในตอนท้ายของส่วน เราจะจดบันทึกเกี่ยวกับวิธีการกำหนดห่วงโซ่ต่ำสุดและสูงสุดโดยใช้เมทริกซ์ของระยะทางที่เชื่อมต่อจุดยอด $i$-th และ $j$-th ในกราฟ

และตอนนี้เราได้ให้คำจำกัดความเพิ่มเติมเกี่ยวกับทฤษฎีกราฟที่เกี่ยวข้องกับระยะห่างระหว่างจุดยอด และซึ่งกำหนดได้ง่ายจากเมตริกซ์ระยะทาง

ความเยื้องศูนย์กลาง$e(v)$ ของจุดยอด $v$ ในกราฟที่เชื่อมต่อกัน $\Gamma$ ถูกกำหนดเป็น $d(u,v)$ สูงสุดสำหรับจุดยอด $u$ ใน $\Gamma$ รัศมี$r(\Gamma)$ คือจุดเยื้องศูนย์ที่เล็กที่สุด โปรดทราบว่าค่าความเยื้องศูนย์ที่ใหญ่ที่สุดเท่ากับเส้นผ่านศูนย์กลางของกราฟ จุดยอด $v$ เรียกว่าจุดยอดกลางของกราฟ $\Gamma$ ถ้า $e(v) = r(\Gamma)$; ศูนย์กลางกราฟ $\Gamma$ คือเซตของจุดยอดกลางทั้งหมด

ดังนั้นสำหรับกราฟ $\Gamma _1$ จากรูปที่ 1 ความเยื้องศูนย์กลางของจุดยอด 13 จะเท่ากับ 2 ($e(13) = 2$) จุดยอด 3, 5 และ 10 จะมีค่าความเยื้องศูนย์เท่ากัน ($e(3) = e(5) = e(10) = 2$) ความเยื้องศูนย์เท่ากับ 2 จะเป็นค่าที่เล็กที่สุดสำหรับกราฟ $\Gamma _1$ นั่นคือ $r(\Gamma _1) = 2$ จุดกึ่งกลางของกราฟ $\Gamma _1$ จะประกอบด้วยจุดยอด 3, 5, 10 และ 13 ความเยื้องศูนย์ที่ใหญ่ที่สุดจะเท่ากับ 3 และจะเท่ากับเส้นผ่านศูนย์กลางของกราฟ $\Gamma _1$ ตามที่ระบุไว้ด้านบน .

สำหรับกราฟ $\Gamma _2$ จากรูปที่ 2 จุดยอด 4 เท่านั้นที่จะมีความเยื้องศูนย์น้อยที่สุด ($e(4) = r(\Gamma _2) = 3$) ดังนั้น จุดกึ่งกลางของกราฟ $\Gamma _2$ จึงประกอบด้วยจุดยอด 4 จุดหนึ่งจุด เส้นผ่านศูนย์กลางของกราฟ $\Gamma _2$ ตามที่ระบุไว้ข้างต้น คือ 6

กราฟ $\Gamma _2$ เป็นต้นไม้ และโครงสร้างของจุดศูนย์กลางของต้นไม้ใดๆ อธิบายได้ด้วยทฤษฎีบทต่อไปนี้

ทฤษฎีบทจอร์แดน-ซิลเวสเตอร์ต้นไม้แต่ละต้นมีจุดศูนย์กลางที่ประกอบด้วยจุดยอดหนึ่งจุดหรือสองจุดที่อยู่ติดกัน

การพิสูจน์.แสดงด้วย $K_1$ กราฟที่ประกอบด้วยจุดยอดเดี่ยวหนึ่งจุด และด้วย $K_2$ กราฟของจุดยอดสองจุดเชื่อมต่อกันด้วยเส้นเชื่อม ตามนิยาม เราตั้งค่า $e(K_1) = r(K_1) = 0$ จากนั้นการยืนยันทฤษฎีบทจะคงไว้สำหรับ $K_1$ และ $K_2$ ขอให้เราแสดงว่าต้นไม้ $T$ ใดๆ มีจุดยอดกลางเหมือนกับต้นไม้ที่ $(T)"$ ได้จาก $T$ โดยลบจุดยอดลอยทั้งหมด เป็นที่ชัดเจนว่าระยะห่างจากจุดยอดที่กำหนด $u$ ไปยังใดๆ จุดสุดยอดอื่นๆ $v$ สามารถเข้าถึงได้ ค่าที่ยิ่งใหญ่ที่สุดเฉพาะในกรณีที่ $v$ เป็นจุดยอดลอย

ดังนั้น ความเยื้องศูนย์กลางของจุดยอดแต่ละจุดของต้นไม้ $(T)"$ จึงน้อยกว่าความเยื้องศูนย์กลางของจุดยอดเดียวกันใน $T$ หนึ่งจุดพอดี ความเยื้องศูนย์ใน $(T)"$ เช่น จุดศูนย์กลางของต้นไม้ $T$ และ $(T)"$ ตรงกัน หากเราดำเนินการลบจุดยอดแขวนต่อไป เราก็จะได้ลำดับของต้นไม้ที่มีจุดศูนย์กลางเดียวกับ $T$ เนื่องจาก $T$ มีค่าจำกัด เราจะต้องไปถึง $K_1$ หรือถึง $K_2$ ไม่ว่าในกรณีใด จุดยอดทั้งหมดของต้นไม้ที่ได้รับด้วยวิธีนี้จะสร้างจุดศูนย์กลางของต้นไม้ ซึ่งประกอบด้วยจุดยอดเดียวหรือสองจุดที่อยู่ติดกัน

ให้เราแสดงวิธีการใช้เมทริกซ์ระยะทางเพื่อกำหนด ตัวอย่างเช่น เส้นทางขั้นต่ำที่เชื่อมต่อจุดยอด 4 กับจุดยอด 8 บนกราฟ $\Gamma _1$ ในเมทริกซ์ $D_1$ องค์ประกอบ $d_(48) = 3$ ลองใช้คอลัมน์ที่ 8 ของเมทริกซ์ $D_1$ และหาองค์ประกอบทั้งหมดของคอลัมน์นี้เท่ากับ 1 ในคอลัมน์ สามารถพบองค์ประกอบดังกล่าวได้อย่างน้อยหนึ่งองค์ประกอบเนื่องจากความเชื่อมโยงของกราฟ $D_1$ ในความเป็นจริงจะมีสามหน่วยดังกล่าวในคอลัมน์ที่ 8 และอยู่ในแถวที่ 5, 6 และ 7 ตอนนี้ให้เราใช้แถวที่ 4 และพิจารณาองค์ประกอบที่อยู่ในคอลัมน์ที่ 5, 6 และ 7 องค์ประกอบเหล่านี้จะเป็น 2, 3 และ 3 ตามลำดับ เฉพาะองค์ประกอบที่อยู่ในคอลัมน์ที่ 5 เท่านั้นที่มีค่าเท่ากับ 2 และเมื่อรวมกับ 1 ซึ่งอยู่ที่ตำแหน่ง (5,8) จะให้ผลรวมเป็น 3 ดังนั้น จุดยอด 5 จึงรวมอยู่ในห่วงโซ่ $\( \(4, ?\), \(? ,5\),\(5,8\)\)$. ตอนนี้ให้เราหาคอลัมน์ที่ 5 ของเมทริกซ์และพิจารณา 1 ของคอลัมน์นี้ เหล่านี้จะเป็นองค์ประกอบที่อยู่ในบรรทัดที่ 3, 6, 7, 8, 10 และ 13 เรากลับไปที่แถวที่ 4 อีกครั้งและดูว่าเฉพาะจุดตัดของคอลัมน์ที่สามและแถวที่ 4 คือ 1 ซึ่งเมื่อรวมกับ 1 ในตำแหน่ง (3,5) ให้ผลรวมเป็น 2 ดังนั้นห่วงโซ่ที่ต้องการจะ เป็น $\( \ (4,3\),\(3,5\),\(5,8\)\)$ เมื่อพิจารณาจากรูปที่ 1 เราเชื่อมั่นในความถูกต้องของโซลูชันที่พบ

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

ให้ G(V,X) เป็นกราฟจำลอง และให้จุดยอด v และ w (v¹w) ของกราฟนี้เชื่อมต่อกันด้วยเส้นทาง จากนั้นจำเป็นต้องมีเส้นทางขั้นต่ำที่เชื่อมต่อจุดยอดเหล่านี้ แสดงความยาวของเส้นทางนี้ d(v, w) เรายังตั้งค่า d(v, v) =0 สำหรับจุดยอดใดๆ vнV; d(v, w) = ¥ หากไม่มีเส้นทางระหว่าง v และ w

ค่า d(v,w) ที่กำหนดด้วยวิธีนี้สำหรับจุดยอดใดๆ ของ v และ w ของกราฟ G(V, X) เรียกว่า ระยะห่างระหว่าง v และ w

จำนวนระยะทางในกราฟที่มีจุดยอด n จุดเท่ากับจำนวนชุดค่าผสม C n 2 .

ให้เชื่อมต่อกราฟ G(V,X) ให้เรากำหนดแนวคิดต่อไปนี้:

เส้นผ่านศูนย์กลางของกราฟ: d(G) = สูงสุด(v, w).

ความเยื้องศูนย์กลาง (ออฟเซ็ตสูงสุด) ของจุดยอด: r(v) = maxd(v, w);

รัศมีกราฟ: r(G) = นาที r(v);

ศูนย์กราฟ: จุดยอดใดๆ vOV ที่ทำให้ r(v) = r(G)

เส้นผ่านศูนย์กลางของกราฟ ความเยื้องศูนย์กลางของจุดยอด รัศมีของกราฟ และจุดกึ่งกลางของกราฟเรียกว่าคุณลักษณะเมตริกของกราฟ

ตัวอย่าง. ค้นหาลักษณะเมตริกของกราฟที่กำหนดโดยไดอะแกรม:

ให้เราหาระยะทางทั้งหมดโดยคำนึงถึงว่า d(v, w) = d(w, v).

จำนวนระยะทางในคอลัมน์ที่กำหนด С 5 2 = 5!/3!2! = 10: d(v 1 , v 2) =1, d(v 1 , v 3) = 2, d(v 1 , v 4) = 2, d(v 1 , v 5) = 3, d(v 2 , v 3) = 1, d(v 2 , v 4) = 1, d(v 2 , v 5) = 2, d(v 3 , v 4) = 1, d(v 3 , v 5) = 2, ง(ข้อ 4 , ข้อ 5) = 1.

เส้นผ่านศูนย์กลางกราฟ d(G) =3.

ความเยื้องศูนย์ของจุดยอด: r(v 1) = 3, r(v 2) = 2, r(v 3) = 2, r(v 4) = 2, r(v 5) = 3

รัศมีกราฟ r(G) = 2.

ศูนย์กราฟ v 2 , v 3 , v 4

3. เส้นทางขั้นต่ำในกราฟที่โหลด

กราฟ G(V, X) เรียกว่าโหลด ถ้าบนชุดขอบของกราฟมีฟังก์ชันที่เรียกว่าฟังก์ชันน้ำหนักที่เชื่อมโยงกับแต่ละขอบ x нX ของกราฟบางจำนวน l(x) ค่า l(x) เรียกว่าความยาวส่วนโค้ง

สามารถกำหนดปริมาณ l(x) ได้ ความหมายที่แตกต่างกัน: ค่าขนส่ง, เวลาเดินทาง, ระยะทางระหว่างจุด, ปริมาณการใช้น้ำมัน ฯลฯ

ผลรวมของความยาวของขอบที่รวมอยู่ในเส้นทางเรียกว่าความยาวของเส้นทาง

โปรดทราบว่าหากสำหรับ x н X l(x) = 1 ทั้งหมด จะถือว่ากราฟไม่โหลด

เส้นทางในกราฟ G(V, X) จากจุดยอด v ถึงจุดยอด w (v¹w) เรียกว่า น้อยที่สุด หากมีความยาวน้อยที่สุดในบรรดาเส้นทางทั้งหมดในกราฟ G(V, X) จากจุดยอด v ถึงจุดยอด w

เราจำกัดตัวเองไว้ที่กราฟซึ่ง l(x)>0

เมื่อค้นหาเส้นทางขั้นต่ำในกราฟที่โหลดด้วย l(x)>0

เราใช้คำสั่งเดียวกันกับกราฟที่ไม่ได้โหลด กล่าวคือ:

เส้นทางที่น้อยที่สุดคือเส้นทางที่เรียบง่าย

พิจารณาปัญหาในการค้นหาเส้นทางขั้นต่ำในกราฟที่โหลด

ให้โหลดกราฟ G(V,X) จำนวนจุดยอด n ³ 2 จำเป็นต้องสร้างเส้นทางขั้นต่ำจาก v 1 ถึง v n .

ให้อัลกอริทึม

ขั้นตอนที่ 1 กำหนดดัชนี a(vi) ให้กับจุดยอดแต่ละจุด: a(v 1) = 0, a(v i) = ¥, i ¹ 1. ระบายสีจุดยอด v 1 และตั้งค่า v = v 1

ขั้นตอนที่ 2 สำหรับแต่ละจุดยอดที่ไม่มีสี v j เปลี่ยนดัชนีตามกฎ:

ก(v j) = นาที (a(v j), a(v) + l(v, v j)).

ระบายสีจุดสุดยอดที่ a(v j) เล็กที่สุด.. และระบายสีขอบที่นำไปสู่โหนดที่เลือก ขั้นตอนนี้จุดสุดยอด v j . ใส่ v = v j .

ขั้นตอนที่ 3 ถ้า v = v j ให้เสร็จสิ้นขั้นตอนตั้งแต่เส้นทางที่สั้นที่สุดจาก v 1 ถึง v n ถ้า v ¹ vn ให้ไปที่ขั้นตอนที่ 2

ความคิดเห็น ขั้นตอนที่ 2 เป็นไปไม่ได้หาก a(v j) = ¥ ทั้งหมด ในกรณีนี้ จุดยอด v n ไม่สามารถเข้าถึงได้

ให้เราใช้อัลกอริทึมข้างต้นกับกราฟที่กำหนดโดยไดอะแกรม ลองหาเส้นทางที่สั้นที่สุดจาก v 1 ถึง v 6 กัน

ขั้นตอนที่ 1 ระบายสีจุดยอด v 1 กำหนดดัชนีให้กับจุดยอด: a(v 1) =0, a(v 2) = a(v 3)=…= a(v n)=¥ เรากำหนดให้ v 1 = v

ก(v 2) = นาที(¥, 0+4) = 4,

ก(v 3) = นาที(¥, 0+7) = 7,

ก(v 4) = นาที(¥, 0+3) = 3,

a(v 5) = นาที (¥, 0+¥) = ¥,

a(v 6) = นาที (¥, 0+¥) = ¥

เราระบายสีจุดสุดยอด v 4 และขอบ (v 1 , v 4 )

ขั้นตอนที่ 3 เนื่องจากจุดยอด v 6 ไม่มีสี เราจึงดำเนินการขั้นตอนที่ 2 โดยตั้งค่า v = v 4

ก(v 2) = นาที(4, 3+¥) = 4,

ก(v 3) = นาที(7, 3+¥) = 7,

ก(v 5) = นาที(¥, 3+3) = 6,

a(v 6) = นาที (¥, 3+¥) = ¥

เราระบายสีจุดสุดยอด v 2 และขอบ (v 1 , v 2 )

ขั้นตอนที่ 3 เนื่องจากจุดยอด v 6 ไม่มีสี เราจึงดำเนินการขั้นตอนที่ 2 โดยตั้งค่า v = v 2

ก(v 3) = นาที(7, 4+3) = 7,

ก(v 5) = นาที(6, 4+2) = 6,

ก(v 6) = นาที (¥, 4+¥) = ¥

เราระบายสีจุดสุดยอด v 5 และขอบ (v 4 , v 5 )

ขั้นตอนที่ 3 เนื่องจากจุดยอด v 6 ไม่มีสี เราจึงดำเนินการขั้นตอนที่ 2 โดยตั้งค่า v = v 5

ก(v 3) = นาที(7, 6+¥) = 7,

a(v 6) = นาที (¥, 6+2) = 8.

เราระบายสีจุดสุดยอด v 3 และขอบ (v 1 , v 3 )

ขั้นตอนที่ 3 เนื่องจากจุดยอด v 6 ไม่มีสี เราจึงดำเนินการขั้นตอนที่ 2 โดยตั้งค่า v = v 3

ก(v 6) = นาที(8, 7+2) = 8.

เราระบายสีจุดสุดยอด v 6 และขอบ (v 5 , v 6 )

เนื่องจากจุดยอด v 6 เป็นสี เราจึงหยุดการทำงาน เราได้เส้นทางขั้นต่ำ v 1 v 4 v 5 v 6 ซึ่งมีความยาวเท่ากับ 8 .

โปรดทราบว่าในกรณีนี้ นี่ไม่ใช่เส้นทางขั้นต่ำเพียงเส้นเดียวสำหรับจุดยอด v 1 และ v 6 เนื่องจาก ในอัลกอริทึมเป็นไปได้ที่จะระบายสีแทนขอบ (v 4 , v 5 ) ขอบ (v 2 , v 5 ) จากนั้นเราจะได้เส้นทางอื่นที่มีความยาวเท่ากัน

4. งานบนต้นไม้

กราฟเรียกว่า acyclic หากไม่มีวัฏจักร

กราฟที่ไม่มีวงจรเรียกว่าฟอเรสต์

ต้นไม้เป็นกราฟวงกลมที่เชื่อมต่อกัน

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

เป็นการง่ายที่จะตรวจสอบว่าแนวคิดเรื่องระยะทางที่แนะนำในลักษณะนี้เป็นไปตามสัจพจน์ของเมตริก:

2. ถ้า ก็ต่อเมื่อ ;

3. ;

4. อสมการรูปสามเหลี่ยมเป็นจริง:

สำหรับจุดยอดคงที่ของกราฟ ระยะทางไปยังจุดยอดที่ไกลที่สุดจากกราฟ: , เรียกว่า ความเยื้องศูนย์ (ขีดสุด การถอด) ท็อปส์ซู

เส้นผ่านศูนย์กลางกราฟเรียกว่าจำนวน เท่ากับระยะทางระหว่างจุดยอดของกราฟที่ห่างจากกันมากที่สุด:

.

โซ่ธรรมดาที่มีความยาว , เรียกว่า เส้นผ่านศูนย์กลาง โซ่. เห็นได้ชัดว่าเส้นผ่านศูนย์กลางของกราฟนั้นเท่ากับเส้นผ่านศูนย์กลางที่ใหญ่ที่สุดในบรรดาความเยื้องศูนย์ของจุดยอดของกราฟ ด้านบนเรียกว่า อุปกรณ์ต่อพ่วง, ถ้า .

ความเยื้องศูนย์ที่เล็กที่สุดของจุดยอดของกราฟที่เชื่อมต่อนั้นเรียกว่า รัศมีและแสดงว่า:

เนื่องจากเส้นผ่านศูนย์กลางของกราฟเท่ากับค่าความเยื้องศูนย์กลางที่ใหญ่ที่สุดของจุดยอด และรัศมีมีขนาดเล็กที่สุด รัศมีของกราฟจึงไม่สามารถมากกว่าเส้นผ่านศูนย์กลางของมันได้ ด้านบนเรียกว่า ศูนย์กลาง, ถ้า . ชุดของจุดศูนย์กลางทั้งหมดของกราฟเรียกว่า ศูนย์กลาง. จุดศูนย์กลางของกราฟสามารถเป็นจุดยอดเดียวหรือหลายจุดก็ได้ มีกราฟที่มีจุดศูนย์กลางตรงกับเซตของจุดยอดทั้งหมด ตัวอย่างเช่น จุดศูนย์กลางของห่วงโซ่อย่างง่ายประกอบด้วยจุดยอดสองจุดสำหรับจุดยอดที่เป็นเลขคู่ และอีกจุดหนึ่งสำหรับจุดยอดเป็นเลขคี่ และจุดยอดทั้งหมดเป็นจุดศูนย์กลางสำหรับวงจรใดๆ

เพื่ออธิบายให้ดูที่กราฟในรูป 4.29. ที่นี่

นั่นเป็นเหตุผล

จุดยอด 2 คือจุดกึ่งกลางของกราฟ และจุดยอดอื่นๆ ทั้งหมดจะอยู่รอบนอก โซ่ 1, 2, 3 เป็นหนึ่งในโซ่ที่มีเส้นผ่านศูนย์กลาง

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

ปัญหาในการหาจุดกึ่งกลางของกราฟพบอย่างต่อเนื่องใน กิจกรรมภาคปฏิบัติ. ตัวอย่างเช่น จุดยอดของกราฟตรงกับหมู่บ้านเล็กๆ และขอบของมันตรงกับถนนระหว่างหมู่บ้าน จำเป็นต้องวางสิ่งเหล่านี้อย่างเหมาะสมที่สุด การตั้งถิ่นฐานสมมติว่าร้านค้า ที่ สถานการณ์ที่คล้ายกันเกณฑ์การเพิ่มประสิทธิภาพมักจะประกอบด้วยการเพิ่มประสิทธิภาพกรณีที่ "แย่ที่สุด" นั่นคือการลดระยะทางจากร้านค้าไปยังหมู่บ้านที่ห่างไกลที่สุด วิธีการเพิ่มประสิทธิภาพนี้เกี่ยวข้องกับการวางร้านค้าในการชำระเงินที่แสดงถึงจุดศูนย์กลางของกราฟ

การข้ามผ่านกราฟ

มีการตั้งข้อสังเกตแล้วว่าจุดเริ่มต้นของทฤษฎีกราฟเกี่ยวข้องกับปัญหาของสะพานKönigsberg ปัญหานี้มีชื่อเสียงในสมัยนั้น ประกอบด้วย สะพานเจ็ดแห่งของเมือง Koenigsberg (ปัจจุบันคือ Kaliningrad) ตั้งอยู่บนแม่น้ำ Pregel ดังแสดงในรูปที่ 4.30 น. ภารกิจคือออกจากบ้านและย้อนกลับโดยผ่านสะพานแต่ละแห่งเพียงครั้งเดียว

เนื่องจากเฉพาะการข้ามสะพานเท่านั้นที่มีความสำคัญในปัญหา ผังเมืองสามารถลดลงเป็นกราฟ (อย่างแม่นยำยิ่งขึ้น มัลติกราฟ) ซึ่งขอบตรงกับสะพานและจุดยอดสอดคล้องกับส่วนต่าง ๆ ของเมืองซึ่งระบุไว้ ตามตัวอักษร (รูปที่ 4.30 ทางด้านขวา) ออยเลอร์แสดงให้เห็นว่าเป็นไปไม่ได้ที่จะผ่านสะพานKönigsbergทั้งหมดเพียงครั้งเดียวแล้วย้อนกลับ ในงานของเขาซึ่งตีพิมพ์ในปี 1736 เขาได้กำหนดและแก้ไขสิ่งต่อไปนี้ ปัญหาที่พบบ่อยทฤษฎีกราฟ: ภายใต้เงื่อนไขใด กราฟที่เชื่อมต่อกันจะมีวัฏจักรที่ผ่านขอบแต่ละด้าน

วัฏจักรในกราฟเรียกว่า ออยเลอร์หากมีขอบทั้งหมดของกราฟ เรียกกราฟที่เชื่อมต่อซึ่งมีวัฏจักรออยเลอร์ ออยเลอร์นับ. สามารถวาดกราฟดังกล่าวได้โดยไม่ต้องยกดินสอขึ้นจากกระดาษและไม่ต้องขีดเส้นซ้ำ

ตัวอย่างเช่น กราฟแสดงในรูป 4.31 เป็นออยเลอร์เพราะมีวัฏจักรออยเลอร์ 1, 2, 3, 4, 5, 6, 4, 2, 6, 1 มีวัฏจักรออยเลอร์อื่นๆ ในกราฟนี้ เป็นที่ชัดเจนว่าสองรอบดังกล่าวแตกต่างกันเฉพาะตามลำดับที่ข้ามผ่านขอบเท่านั้น

ทฤษฎีบท 4.7(แอล. ออยเลอร์, 1736 .) กราฟที่เชื่อมต่อคือออยเลอร์ก็ต่อเมื่อองศาของจุดยอดทั้งหมดเป็นเลขคู่

ลูกโซ่ ก็เรียก ออยเลอร์หากมีขอบทั้งหมดของกราฟ

ทฤษฎีบท 4.8(แอล. ออยเลอร์, 1736 .) มัลติกราฟมีห่วงโซ่ออยเลอร์ก็ต่อเมื่อเชื่อมต่อกันและจำนวนจุดยอดของระดับคี่คือ 0 หรือ 2

แม้จะมี "ความคล้ายคลึง" ในคำจำกัดความของวัฏจักรออยเลอร์และแฮมิลตัน ทฤษฎีที่เกี่ยวข้องซึ่งกำหนดเกณฑ์การดำรงอยู่และอัลกอริทึมสำหรับการค้นหาวัฏจักรดังกล่าวก็แทบไม่มีเหมือนกัน เทเรมของออยเลอร์ (ทฤษฎีบท 4.7)ทำให้ง่ายต่อการพิจารณาว่ากราฟเป็นออยเลอร์หรือไม่ อัลกอริทึมได้รับการพัฒนาซึ่งทำให้ง่ายต่อการค้นหาวัฏจักรออยเลอร์ของกราฟออยเลอร์ เท่าที่เกี่ยวข้องกับกราฟแฮมิลตัน สถานการณ์ที่นี่แตกต่างออกไป ตามกฎแล้ว เป็นการยากที่จะตอบคำถามว่ากราฟใดกราฟหนึ่งเป็นแฮมิลตันหรือไม่ เกณฑ์ทั่วไปซึ่งคล้ายกับเกณฑ์ออยเลอร์ไม่มีอยู่ที่นี่ แต่เมื่อปรากฎว่า ในเซตของกราฟทั้งหมด มีกราฟออยเลอร์เพียงเล็กน้อยเท่านั้น แต่มีกราฟแฮมิลตันค่อนข้างมาก