กราฟกำกับ

ในรูปแบบทางการกราฟกำกับคือคู่ลำดับG = ( V , A )โดยที่^[1]

• Vเป็นชุดที่มีองค์ประกอบที่เรียกว่าจุด , โหนดหรือจุด ;
• คือชุดของคู่อันดับของจุดที่เรียกว่าโค้ง , ขอบกำกับ (บางครั้งเพียงแค่ขอบกับชุดที่สอดคล้องกันชื่อEแทน), ลูกศรหรือเส้นกำกับ

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

คำนิยามดังกล่าวไม่อนุญาตให้นำกราฟที่จะมีลูกศรหลายที่มีแหล่งที่มาและเป้าหมายเดียวกันโหนด แต่ผู้เขียนบางคนคิดว่าคำนิยามที่กว้างขึ้นที่ช่วยให้การกำกับกราฟจะมีโค้งหลายอย่างเช่น (กล่าวคือพวกเขาช่วยให้ชุดโค้งจะเป็นMultiSet ) . โดยเฉพาะอย่างยิ่งหน่วยงานเหล่านี้ได้รับการแก้ไขเป็นmultigraphs กำกับ (หรือmultidigraphs )
ในทางกลับกันคำจำกัดความดังกล่าวอนุญาตให้กราฟกำกับมีลูป (นั่นคือส่วนโค้งที่เชื่อมต่อโหนดโดยตรงกับตัวมันเอง) แต่ผู้เขียนบางคนพิจารณาคำจำกัดความที่แคบกว่าซึ่งไม่อนุญาตให้กราฟกำกับมีการวนซ้ำ ^[2]โดยเฉพาะอย่างยิ่งกราฟที่กำหนดทิศทางโดยไม่มีการวนซ้ำจะถูกกำหนดให้เป็นกราฟกำกับอย่างง่ายในขณะที่กราฟกำกับที่มีการวนซ้ำจะถูกกำหนดเป็นกราฟแบบลูป(ดูหัวข้อประเภทของกราฟที่กำหนดทิศทาง )

คลาสย่อย

กราฟ acyclic ที่กำหนดทิศทางอย่างง่าย

การแข่งขันบนจุดยอด 4 จุด

• กราฟกำกับแบบสมมาตรคือกราฟที่กำหนดทิศทางโดยที่ขอบทั้งหมดจะถูกเสนอราคา (นั่นคือสำหรับลูกศรทุกลูกที่เป็นของกราฟลูกศรผกผันที่เกี่ยวข้องจะเป็นของมันด้วย)
• กราฟที่กำหนดทิศทางอย่างง่ายคือกราฟกำกับที่ไม่มีการวนซ้ำ (ลูกศรที่เชื่อมต่อจุดยอดโดยตรงกับตัวมันเอง) และไม่มีลูกศรหลายลูกที่มีโหนดต้นทางและปลายทางเดียวกัน เป็นที่รู้จักอยู่แล้วในกรณีของลูกศรหลายกิจการมักจะ addressed เป็นmultigraph กำกับ นักเขียนบางคนอธิบาย digraphs กับลูปเป็นห่วง digraphs ^[2]
  • กราฟที่กำหนดทิศทางแบบสมบูรณ์คือกราฟที่กำหนดทิศทางอย่างง่ายโดยจุดยอดแต่ละคู่จะเชื่อมต่อด้วยคู่สมมาตรของส่วนโค้งที่กำหนดทิศทาง (เทียบเท่ากับกราฟที่ไม่ได้กำหนดทิศทางที่สมบูรณ์โดยขอบจะถูกแทนที่ด้วยคู่ของส่วนโค้งผกผัน) ตามมาว่ากราฟที่สมบูรณ์จะสมมาตร
  • digraphs multipartite Semicompleteมี digraphs ง่ายในการที่ชุดจุดสุดยอดเป็นพาร์ทิชันเป็นชุด partite ดังกล่าวว่าสำหรับคู่ของจุดทุกxและy ที่ในชุด partite ที่แตกต่างกันมีความโค้งระหว่างxและy ที่ โปรดทราบว่าอาจมีหนึ่งส่วนโค้งระหว่างxและyหรือสองส่วนโค้งในทิศทางตรงกันข้าม ^[3]
  • Digraphs เซมิคอมสมบูรณ์เป็นกราฟแบบง่ายที่มีส่วนโค้งระหว่างจุดยอดแต่ละคู่ Digraph แบบเซมิโคลอนทุกตัวคือไดกราฟหลายส่วนที่เป็นเซมิคอนดักเตอร์โดยที่จำนวนจุดยอดจะเท่ากับจำนวนของเซตพาร์ไทต์ ^[4]
  • digraphs กึ่งสกรรมกริยามี digraphs ง่ายๆที่ทุกสามx , Y , Zของจุดที่แตกต่างกันกับโค้งจากxไปYและYจะZมีความโค้งระหว่างxและZ โปรดทราบว่าอาจมีเพียงหนึ่งส่วนโค้งระหว่างxและzหรือสองส่วนโค้งในทิศทางตรงกันข้าม Digraph แบบเซมิไฟนอลคือไดกราฟกึ่งสกรรมกริยา มีส่วนขยายของ digraphs กึ่งสกรรมกริยาที่เรียกว่าk -quasi-transitive digraphs ^[5]
  • กราฟเชิงเส้นคือกราฟที่กำหนดทิศทางโดยไม่มีขอบเสนอราคา (กล่าวคือมากที่สุดหนึ่งใน ( x , y )และ ( y , x )อาจเป็นลูกศรของกราฟ มันตามที่นำกราฟเป็นกราฟที่มุ่งเน้นและถ้าหากมันไม่ได้ใด ๆ2 วงจร ^[6]
    • ทัวร์นาเมนต์จะเน้นกราฟได้โดยการเลือกทิศทางสำหรับแต่ละขอบในการไม่มีทิศทางกราฟบริบูรณ์ โปรดทราบว่าทัวร์นาเมนต์เป็นรูปแบบย่อส่วนที่สมบูรณ์ ^[7]
    • กำกับการแสดงกราฟวัฏจักร (DABs ความ) เป็นผู้กำกับกราฟที่ไม่มีรอบกำกับ ^[8]
      • Multitreesคือ DAG ที่ไม่มีเส้นทางกำกับที่แตกต่างกันสองเส้นทางจากจุดยอดเริ่มต้นเดียวกลับมาบรรจบกันที่จุดยอดสิ้นสุดเดียวกัน
      • ต้นไม้เชิงเส้นหรือ polytreesเป็น DAGที่เกิดขึ้นจากการวางแนวขอบของกราฟแบบไม่กำหนดทิศทาง
        • ต้นไม้ที่หยั่งรากเป็นต้นไม้ที่เน้นที่ขอบทั้งหมดของต้นไม้ที่ไม่ได้กำหนดทิศทางจะถูกนำออกจากหรือไปทางราก (เรียกว่าต้นนอกและในต้นไม้ตามลำดับ

Digraphs ที่มีคุณสมบัติเสริม

• กราฟกำกับแบบถ่วงน้ำหนัก (หรือที่เรียกว่าเครือข่ายที่กำหนดทิศทาง ) คือกราฟกำกับ (แบบง่าย) ที่มีน้ำหนักที่กำหนดให้กับลูกศรซึ่งคล้ายกับกราฟถ่วงน้ำหนัก (ซึ่งเรียกอีกอย่างว่าเครือข่ายที่ไม่ได้กำหนดทิศทางหรือเครือข่ายแบบถ่วงน้ำหนัก ) ^[2]
  • โฟลว์เน็ตเวิร์กคือกราฟกำกับแบบถ่วงน้ำหนักโดยมีโหนดสองโหนดที่แตกต่างกันแหล่งที่มาและซิงก์
• กราฟกำกับรูท (หรือที่เรียกว่ากราฟการไหล ) คือกราฟที่มีจุดยอดถูกแยกแยะเป็นรูท
  • กราฟการควบคุมโฟลว์เป็นกราฟแบบรูทที่ใช้ในวิทยาการคอมพิวเตอร์เพื่อเป็นตัวแทนของเส้นทางที่อาจเคลื่อนที่ผ่านโปรแกรมในระหว่างการดำเนินการ
• กราฟการไหลของสัญญาณคือกราฟกำกับซึ่งโหนดแสดงถึงตัวแปรของระบบและกิ่งก้าน (ขอบโค้งหรือลูกศร) แสดงถึงการเชื่อมต่อที่ใช้งานได้ระหว่างคู่ของโหนด
• โฟลว์กราฟเป็นกราฟที่เกี่ยวข้องกับชุดของพีชคณิตเชิงเส้นหรือสมการเชิงอนุพันธ์
• แผนภาพรัฐจะกำกับ multigraphsที่เป็นตัวแทนของเครื่องสถานะ จำกัด
• แผนภาพเชิงสับเปลี่ยนคือไดกราฟที่ใช้ในทฤษฎีหมวดหมู่โดยจุดยอดเป็นตัวแทนของวัตถุ (ทางคณิตศาสตร์) และลูกศรแสดงถึงสัณฐานวิทยาโดยคุณสมบัติที่พา ธ ที่กำหนดทิศทางทั้งหมดที่มีจุดเริ่มต้นและจุดสิ้นสุดเดียวกันนำไปสู่ผลลัพธ์เดียวกันตามองค์ประกอบ
• ในทฤษฎีของกลุ่ม Lieนั้นquiver Qคือกราฟกำกับที่ทำหน้าที่เป็นโดเมนของดังนั้นการแสดงลักษณะของรูปร่างการแทนค่า V ที่กำหนดให้เป็นfunctorโดยเฉพาะอ็อบเจ็กต์ของประเภท functor FinVct _K ^{F ( Q )}โดยที่F ( Q ) เป็นหมวดหมู่ฟรีบนQประกอบด้วยเส้นทางในQและ FinVct _Kเป็นหมวดหมู่ของการ จำกัด มิติเวกเตอร์พื้นที่กว่าฟิลด์ K การแสดงของฉลากสั่นจุดที่มีช่องว่างเวกเตอร์และขอบ (และด้วยเหตุนี้เส้นทาง) เข้ากันได้กับการเปลี่ยนแปลงเชิงเส้นระหว่างพวกเขาและเปลี่ยนผ่านการเปลี่ยนแปลงทางธรรมชาติ

กราฟเชิงเส้นพร้อมเมทริกซ์อุบัติการณ์ที่สอดคล้องกัน

ส่วนโค้ง( x , y )ถือว่าถูกนำจาก x ไปยัง y ; yเรียกว่าหัวและxเรียกว่าหางของส่วนโค้ง Yมีการกล่าวถึงเป็นทายาทโดยตรงของxและxมีการกล่าวถึงเป็นบรรพบุรุษโดยตรงของปี หากเส้นทางนำจากxไปปีแล้วปีมีการกล่าวถึงเป็นทายาทของxและสามารถเข้าถึงได้จากxและxมีการกล่าวถึงเป็นบรรพบุรุษของปี โค้ง( Y , x )ที่เรียกว่าโค้งตรงกันข้ามของ( x , Y )

เมทริกซ์ถ้อยคำของ multidigraph กับลูปเป็นจำนวนเต็มมูลค่าเมทริกซ์ที่มีแถวและคอลัมน์ที่สอดคล้องกับจุดที่รายการ nondiagonal _IJคือจำนวนของโค้งจากจุดสุดยอดผมจะจุดสุดยอดเจและรายการแนวทแยง_iiเป็นจำนวน ของลูปที่จุดสุดยอดผม เมทริกซ์ adjacency ของกราฟกำกับไม่ซ้ำกันกับการเปลี่ยนแปลงของแถวและคอลัมน์ที่เหมือนกัน

ตัวแทนเมทริกซ์อีกกราฟกำกับเป็นของเมทริกซ์อุบัติการณ์

ดูทิศทางสำหรับคำจำกัดความเพิ่มเติม

กราฟกำกับที่มีจุดยอด (indegree, outdegree)

สำหรับยอดจำนวนหัวปิดให้บริการอยู่ใกล้เคียงกับจุดสุดยอดที่เรียกว่าindegreeของจุดสุดยอดและจำนวนหางปลายอยู่ใกล้เคียงกับจุดสุดยอดคือมันoutdegree (เรียกว่าปัจจัยที่แผ่กิ่งก้านต้นไม้)

ให้G = ( V , )และวี ∈ V ดัชนีของvแสดงถึง deg ^- ( v ) และค่า outdegree แสดงถึง deg ⁺ ( v )

จุดยอดที่มีdeg ^- ( v ) = 0เรียกว่าแหล่งที่มาเนื่องจากเป็นจุดเริ่มต้นของส่วนโค้งขาออกแต่ละส่วน ในทำนองเดียวกันจุดยอดที่มีdeg ⁺ ( v ) = 0เรียกว่าซิงก์เนื่องจากเป็นจุดสิ้นสุดของส่วนโค้งขาเข้าแต่ละส่วน

สูตรผลรวมการศึกษาระดับปริญญากล่าวว่าสำหรับกราฟกำกับ

${\ displaystyle \ sum _ {v \ in V} \ deg ^ {-} (v) = \ sum _ {v \ in V} \ deg ^ {+} (v) = | A |.}$

หากทุกจุดสุดยอดวี ∈ V , องศา⁺ ( V ) = องศา^- ( วี )กราฟที่เรียกว่าสมดุลกราฟ ^[9]

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

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

กราฟกำกับจะเชื่อมต่ออย่างอ่อน (หรือเพียงแค่เชื่อมต่อ^[10] ) ถ้าไม่มีทิศทางกราฟพื้นฐานได้โดยการเปลี่ยนขอบกำกับทั้งหมดของกราฟไม่มีทิศทางที่มีขอบเป็นกราฟที่เกี่ยวโยงกัน

กราฟกำกับจะเชื่อมต่ออย่างยิ่งหรือที่แข็งแกร่งถ้ามีเส้นทางกำกับจากxไปY (และจากปีที่จะx ) สำหรับคู่ของจุดทุก( x , Y ) ส่วนประกอบที่แข็งแกร่งเป็นสูงสุด subgraphs เชื่อมต่ออย่างยิ่ง

กราฟรูทที่เชื่อมต่อ(หรือโฟลว์กราฟ ) คือกราฟที่มีเส้นทางตรงไปยังทุกจุดยอดจากจุดยอดรากที่แตกต่างกัน

• ความสัมพันธ์แบบไบนารี
• กราฟ Coates
• ผังงาน DRAKON
• แผนภูมิการไหล
• อภิธานศัพท์ทฤษฎีกราฟ
• ทฤษฎีกราฟ
• กราฟ (ชนิดข้อมูลนามธรรม)
• ทฤษฎีเครือข่าย
• ปฐมนิเทศ
• สั่งของล่วงหน้า
• การเรียงลำดับโทโพโลยี
• เปลี่ยนกราฟ
• กราฟข้อ จำกัด แนวตั้ง
• ชุดทรงกลม

• บัง - เจนเซ่น, เยอร์เกน; Gutin, Gregory (2000), Digraphs: Theory, Algorithms and Applications , Springer , ISBN 1-85233-268-9
  (ฉบับแก้ไขครั้งที่ 1 ของปี 2550 มีให้บริการฟรีบนเว็บไซต์ของผู้เขียนฉบับที่ 2 ปรากฏในปี 2552 ISBN  1-84800-997-6 )
• บัง - เจนเซ่น, เยอร์เกน; Gutin, Gregory (2018), Classes of Directed Graphs , Springer , ISBN 3319718401.
• บอนด์ดีจอห์นเอเดรียน ; Murty, USR (1976), Graph Theory with Applications , North-Holland, ISBN 0-444-19451-7.
• Diestel, Reinhard (2005), Graph Theory (3rd ed.), Springer , ISBN 3-540-26182-6 (ฉบับที่ 3 แบบอิเล็กทรอนิกส์มีให้บริการฟรีบนเว็บไซต์ของผู้เขียน)
• แฮรี่แฟรงค์ ; นอร์แมนโรเบิร์ตซี; Cartwright, Dorwin (1965), แบบจำลองโครงสร้าง: บทนำสู่ทฤษฎีกราฟกำกับ , นิวยอร์ก: ไวลีย์.
• จำนวนกราฟกำกับ (หรือกราฟกำกับ) ที่มีโหนดจากสารานุกรมออนไลน์ของลำดับจำนวนเต็ม