28 Menger's theoremWe now discuss a

28 Menger's theorem
We now discuss a theorem that is closely related to Hall's theorem and has far-reaching practical applications. This theorem, due to K. Menger, concerns the number of paths connecting two given vertices v and w in a graph G. We may ask for the maximum number of paths from v to w, no two of which have an edge in common - such paths are called edge-disjoint paths. Alternatively, we may ask for the maximum number of paths from v to w, no two of which have a vertex in common, except, of course, v and w - these are called vertex-disjoint paths. For example, in the graph of Fig.28.1, there are four edge-disjoint paths and two vertex-disjoint ones.

ผลลัพธ์ (ไทย) 1:

ทฤษฎีบท 28 Mengerเราตอนนี้กล่าวถึงทฤษฎีบทที่เกี่ยวข้องอย่างใกล้ชิดกับทฤษฎีบทของฮอลล์ และมีกว้างขวางประยุกต์ใช้งานจริง ทฤษฎีบทนี้ เนื่องจากคุณ Menger เกี่ยวข้องกับหมายเลขของเส้นทางที่เชื่อมต่อสองกำหนดจุดยอด v และ w เป็นกราฟกรัม เราอาจขอเส้นทางจาก v กับ w จำนวนสองซึ่งไม่มีขอบเหมือนกัน - เส้นทางดังกล่าวเรียกว่าเส้นขอบ disjoint อีกวิธีหนึ่งคือ เราอาจขอหมายเลขสูงสุดของเส้นทางจาก v กับ w ไม่มีสองที่มีจุดยอดร่วมกัน ยก เว้น แน่นอน v และ w - เหล่านี้เรียกว่าจุดยอด disjoint เส้นทาง เช่น ในกราฟของ Fig.28.1 มีสี่ disjoint ขอบเส้นทางและจุดยอด disjoint สองคน

ผลลัพธ์ (ไทย) 2:

28 ทฤษฎีบท Menger ของ
ตอนนี้เราหารือทฤษฎีบทที่เกี่ยวข้องอย่างใกล้ชิดกับทฤษฎีบทฮอลล์และได้ไกลถึงการใช้งานในทางปฏิบัติ ทฤษฎีบทนี้เนื่องจากเค Menger กังวลจำนวนเส้นทางเชื่อมต่อสองจุดรับวี W ในกราฟกรัมเราอาจขอจำนวนสูงสุดของเส้นทางจาก v เพื่อ W ไม่มีสองซึ่งมีขอบในการร่วมกันนั้น - เส้นทางดังกล่าวจะเรียกว่าเส้นทางขอบเคลื่อน หรืออีกวิธีหนึ่งที่เราอาจจะขอจำนวนสูงสุดของเส้นทางจาก v เพื่อ W ไม่มีสองที่มีจุดสุดยอดในการร่วมกันยกเว้นของหลักสูตร V และ W - เหล่านี้เป็นเส้นทางที่เรียกว่าจุดสุดยอดเคล็ด- ยกตัวอย่างเช่นในกราฟของ Fig.28.1 มีสี่เส้นทางขอบเคลื่อนและสองคนจุดสุดยอดเคล็ด-

ผลลัพธ์ (ไทย) 3:

ทฤษฎีบทของ 28 เมนเจอร์ตอนนี้เราจะหารือเกี่ยวกับทฤษฎีบทที่เกี่ยวข้องอย่างใกล้ชิดกับทฤษฎีบทของสมาคม และได้ทรงปฏิบัติงาน ทฤษฎีบทนี้เนื่องจากเคเมนเจอร์ ข้อสงสัย หมายเลขของเส้นทางการเชื่อมต่อสองให้จุดยอด V และ W ในกราฟ G . เราอาจจะถามสำหรับจำนวนสูงสุดของเส้นทางจาก V w , ไม่มีสองซึ่งมีขอบในทั่วไป - เส้นทางดังกล่าวเรียกว่ายู่ริมทางเดิน หรือเราอาจจะถามสำหรับจำนวนสูงสุดของเส้นทางจาก V w , ไม่มีสองซึ่งมีจุดยอดร่วมกัน แน่นอน ยกเว้น V และ W - เหล่านี้เรียกว่าจุดยอดที่ไม่ต่อเนื่องกัน . ตัวอย่างเช่น ในกราฟของ fig.28.1 มี 4 เส้นทางและจุดยอดสองขอบไม่ต่อเนื่องไม่ต่อเนื่องที่