ในสาขาทฤษฎีกราฟทางคณิตศาสตร์กราฟแบบมีเครื่องหมายคือกราฟที่แต่ละเส้นเชื่อมมีเครื่องหมายบวกหรือลบ

กราฟที่มีเครื่องหมายจะสมดุลก็ต่อเมื่อผลคูณของเครื่องหมายขอบรอบแต่ละวงจรเป็นบวก ชื่อ "กราฟที่มีเครื่องหมาย" และแนวคิดเรื่องความสมดุลปรากฏขึ้นครั้งแรกในบทความทางคณิตศาสตร์ของFrank Hararyในปี 1953 ^{[ 1 ]} Dénes Kőnigได้ศึกษาแนวคิดที่เทียบเท่ากันในปี 1936 ภายใต้คำศัพท์ที่แตกต่างกัน แต่ไม่ได้ตระหนักถึงความเกี่ยวข้องของกลุ่มเครื่องหมาย^{[ 2 ]} ที่ศูนย์พลวัตกลุ่มแห่งมหาวิทยาลัยมิชิแกนDorwin Cartwrightและ Harary ได้ขยาย ทฤษฎีทางจิตวิทยาของ ความสมดุล ในสามเหลี่ยมแห่งความรู้สึก ของFritz Heiderไปสู่ทฤษฎีทางจิตวิทยาของความสมดุลในกราฟที่มีเครื่องหมาย^{[ 3 ] [ 4 ]}

กราฟที่มีเครื่องหมายได้รับการค้นพบใหม่หลายครั้งเนื่องจากปรากฏขึ้นตามธรรมชาติในหลายพื้นที่ที่ไม่เกี่ยวข้องกัน^{[ 5 ]} ตัวอย่างเช่น กราฟเหล่านี้ช่วยให้สามารถอธิบายและวิเคราะห์เรขาคณิตของเซตย่อยของระบบราก แบบคลาสสิก ได้ กราฟเหล่านี้ปรากฏในทฤษฎีกราฟเชิงโทโพโลยีและทฤษฎีกลุ่ม กราฟ เหล่านี้เป็นบริบทตามธรรมชาติสำหรับคำถามเกี่ยวกับวัฏจักร คี่และคู่ ในกราฟ กราฟเหล่านี้ปรากฏในการคำนวณ พลังงาน สถานะพื้นฐาน ใน แบบจำลอง Isingที่ไม่ใช่แม่เหล็กเฟอร์โรแมกเนติก ซึ่งจำเป็นต้องค้นหาเซตขอบที่สมดุลที่ใหญ่ที่สุดใน Σ กราฟเหล่านี้ถูกนำไปใช้กับการจำแนกข้อมูลในการ จัดกลุ่มความสัมพันธ์

เครื่องหมายของเส้นทางเป็นผลคูณของเครื่องหมายของขอบ ดังนั้นเส้นทางจะเป็นบวกก็ต่อเมื่อมีจำนวนขอบลบเป็นเลขคู่ (โดยที่ศูนย์เป็นเลขคู่) ในทฤษฎีสมดุล ทางคณิตศาสตร์ ของแฟรงค์ ฮารารีกราฟที่มีเครื่องหมายจะสมดุลเมื่อทุกวงจรเป็นบวก ฮารารีพิสูจน์ว่ากราฟที่มีเครื่องหมายจะสมดุลเมื่อ (1) สำหรับทุกคู่ของโหนด เส้นทางทั้งหมดระหว่างโหนดเหล่านั้นมีเครื่องหมายเดียวกัน หรือ (2) จุดยอดแบ่งออกเป็นคู่ของเซตย่อย (อาจว่างเปล่า) แต่ละเซตย่อยประกอบด้วยขอบบวกเท่านั้น แต่เชื่อมต่อกันด้วยขอบลบ^{[ 1 ]}มันเป็นการขยายทฤษฎีบทที่ว่ากราฟธรรมดา (ไม่มีเครื่องหมาย) เป็นกราฟสองส่วนก็ต่อเมื่อทุกวงจรมีความยาวเป็นเลขคู่

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

ทฤษฎีบทที่อ่อนกว่า แต่มีการพิสูจน์ที่ง่ายกว่า คือ ถ้าวัฏจักร 3 ทุกวงในกราฟสมบูรณ์ที่มีเครื่องหมายเป็นบวก กราฟนั้นจะสมดุล สำหรับการพิสูจน์ ให้เลือกโหนดn ใดๆ แล้ววางโหนดนั้นและโหนดทั้งหมดที่เชื่อมต่อกับnด้วยขอบบวกไว้ในกลุ่มหนึ่ง เรียกว่าAและโหนดทั้งหมดที่เชื่อมต่อกับnด้วยขอบลบไว้ในอีกกลุ่มหนึ่ง เรียกว่าBเนื่องจากเป็นกราฟสมบูรณ์ โหนดสองโหนดทุกคู่ในAจะต้องเป็นเพื่อนกัน และโหนดสองโหนดทุกคู่ในBจะต้องเป็นเพื่อนกัน มิฉะนั้นจะมีวัฏจักร 3 วงที่ไม่สมดุล (เนื่องจากเป็นกราฟสมบูรณ์ ขอบลบใดๆ ก็ตามจะทำให้เกิดวัฏจักร 3 วงที่ไม่สมดุล) ในทำนองเดียวกัน ขอบลบทั้งหมดจะต้องเชื่อมระหว่างสองกลุ่ม^{[ 6 ]}

ดัชนีความขัดแย้ง (เดิมเรียกว่าดัชนีสมดุลเส้น^{[ 7 ]} ) ของ Σ คือจำนวนขอบที่น้อยที่สุดซึ่งการลบ หรือเทียบเท่ากับการกลับเครื่องหมาย (ทฤษฎีบทของ Harary ^{[ 7 ]} ) ทำให้ Σ สมดุล เหตุผลของความเท่าเทียมกันคือดัชนีความขัดแย้งเท่ากับจำนวนขอบที่น้อยที่สุดซึ่งการปฏิเสธ (หรือเทียบเท่ากับการลบ) ทำให้ Σ สมดุล

อีกวิธีหนึ่งในการอธิบายดัชนีความคับข้องใจคือ มันคือจำนวนขอบที่น้อยที่สุดที่ครอบคลุมวงจรลบทั้งหมด ปริมาณนี้เรียกว่าจำนวน การครอบคลุมวงจรลบ

มีคำจำกัดความที่เทียบเท่ากันอีกแบบหนึ่ง (ซึ่งสามารถพิสูจน์ได้ง่ายโดยการสลับ) กำหนดค่าให้กับแต่ละจุดยอดเป็น +1 หรือ −1 เราเรียกสิ่งนี้ว่าสถานะของ Σ ขอบจะเรียกว่าพึงพอใจหากเป็นค่าบวกและจุดปลายทั้งสองมีค่าเดียวกัน หรือเป็นค่าลบและจุดปลายมีค่าตรงข้าม ขอบที่ไม่พึงพอใจเรียกว่าขัดข้องจำนวนขอบขัดข้องที่น้อยที่สุดในทุกสถานะคือดัชนีความขัดข้อง คำจำกัดความนี้ได้รับการแนะนำครั้งแรกในสัญกรณ์ที่แตกต่างกันโดย Abelson และ Rosenberg ภายใต้ชื่อ (ที่ล้าสมัย) ความซับซ้อน [ ^{8 ] ส่วน} เติมเต็มของเซตดังกล่าวคือกราฟย่อยที่สมดุลของ Σ ที่มีขอบที่เป็นไปได้มากที่สุด

การหาค่าดัชนีความคับข้องใจเป็นปัญหา NP-hard

เราสามารถเห็นความซับซ้อนแบบ NP-hard ได้จากการสังเกตว่าดัชนีความขัดแย้งของกราฟที่มีเครื่องหมายเป็นลบทั้งหมดนั้นเหมือนกับ ปัญหา การตัดสูงสุดในทฤษฎีกราฟ ซึ่งเป็นปัญหา NP-hard เช่น กัน

ดัชนีความขัดแย้งมีความสำคัญในแบบจำลองของสปินกลาส หรือ แบบจำลองไอซิงแบบผสมในแบบจำลองนี้ กราฟที่มีเครื่องหมายจะคงที่ สถานะประกอบด้วยการกำหนด "สปิน" ให้กับแต่ละจุดยอด ไม่ว่าจะเป็น "ขึ้น" หรือ "ลง" เราคิดว่าสปินขึ้นคือ +1 และสปินลงคือ −1 ดังนั้น แต่ละสถานะจึงมีจำนวนขอบที่ขัดแย้งกัน พลังงานของสถานะจะมากขึ้นเมื่อมีขอบที่ขัดแย้งกันมากขึ้น ดังนั้นสถานะพื้นฐานจึงเป็นสถานะที่มีพลังงานที่ขัดแย้งกันน้อยที่สุด ดังนั้น ในการหาพลังงานสถานะพื้นฐานของ Σ จึงต้องหาดัชนีความขัดแย้ง

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

คำถามพื้นฐานสามข้อเกี่ยวกับกราฟที่มีเครื่องหมายคือ: กราฟนั้นสมดุลหรือไม่? ขนาดที่ใหญ่ที่สุดของเซตขอบที่สมดุลในกราฟนั้นคือเท่าใด? จำนวนจุดยอด ที่น้อยที่สุด ที่ต้องลบออกเพื่อให้กราฟสมดุลคือเท่าใด? คำถามแรกนั้นง่ายต่อการแก้ไขในเวลาพหุนาม คำถามที่สองเรียกว่าดัชนีความขัดแย้งหรือ ปัญหา กราฟย่อยที่สมดุลสูงสุดเป็นปัญหาNP-hardเนื่องจากกรณีพิเศษของมัน (เมื่อขอบทั้งหมดของกราฟเป็นลบ) คือปัญหาMaximum Cut ซึ่งเป็นปัญหา NP- hard คำถามที่สามเรียกว่าจำนวนความขัดแย้งหรือ ปัญหา กราฟย่อยที่เหนี่ยวนำที่สมดุลสูงสุดซึ่งก็เป็นปัญหาNP-hard เช่นกัน ดูเช่น^{[ 9 ]}

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

เฟรมแมทรอยด์ (หรือแมทรอยด์กราฟิกแบบมีเครื่องหมาย ) M ( G ) มีเซตพื้นฐานเป็นเซตขอบE [ ^{10 ] เซต} ขอบจะเป็นอิสระหากแต่ละส่วนประกอบไม่มีวงกลมหรือมีวงกลมเพียงวงเดียวซึ่งเป็นลบ (ในทฤษฎีแมทรอยด์ ขอบครึ่งวงจะทำหน้าที่เหมือนวงวนลบ) วงจรของแมทรอยด์อาจเป็นวงกลมบวกหรือวงกลมลบสองวงพร้อมกับเส้นทางเชื่อมต่อแบบง่าย โดยที่วงกลมทั้งสองวงจะไม่ทับซ้อนกัน (ในกรณีนี้ เส้นทางเชื่อมต่อจะมีปลายด้านหนึ่งร่วมกันกับแต่ละวงกลมและไม่ทับซ้อนกับทั้งสองวง) หรือมีจุดยอดร่วมกันเพียงจุดเดียว (ในกรณีนี้ เส้นทางเชื่อมต่อคือจุดยอดนั้น) อันดับของเซตขอบSคือn − bโดยที่nคือจำนวนจุดยอดของGและbคือจำนวนส่วนประกอบที่สมดุลของSโดยนับจุดยอดที่แยกเดี่ยวเป็นส่วนประกอบที่สมดุล แมทรอยด์นี้คือคอลัมน์แมทรอยด์ของเมทริกซ์เหตุการณ์ของกราฟแบบมีเครื่องหมาย ด้วยเหตุนี้จึงอธิบายถึงความสัมพันธ์เชิงเส้นของรากในระบบรากแบบคลาสสิก

แมทรอยด์ยกขยายL ₀ ( G ) มีเซตพื้นฐานเป็นเซตE ₀ซึ่งเป็นการรวมกันของเซตขอบEกับจุดพิเศษซึ่งเราใช้สัญลักษณ์e ₀แมทรอยด์ยกL ( G ) คือแมทรอยด์ยกขยายที่จำกัดอยู่บนEจุดพิเศษนี้ทำหน้าที่เหมือนลูปเชิงลบ ดังนั้นเราจึงอธิบายเฉพาะแมทรอยด์ยกเท่านั้น เซตขอบจะเป็นอิสระหากไม่มีวงกลมหรือมีวงกลมเพียงวงเดียวซึ่งเป็นลบ (นี่คือกฎเดียวกันกับที่ใช้แยกกันกับแต่ละส่วนประกอบในแมทรอยด์กราฟิกแบบมีเครื่องหมาย) วงจรแมทรอยด์คือวงกลมบวกหรือวงกลมลบสองวงที่แยกจากกันหรือมีจุดยอดร่วมกันเพียงจุดเดียว อันดับของเซตขอบSคือn − c + ε โดยที่cคือจำนวนส่วนประกอบของSนับรวมจุดยอดที่แยกเดี่ยว และ ε คือ 0 ถ้าSสมดุลและ 1 ถ้าไม่สมดุล

บางครั้งเครื่องหมายจะถูกกำหนดให้เป็น +1 และ −1 ซึ่งเป็นเพียงความแตกต่างของสัญลักษณ์เท่านั้น หากเครื่องหมายยังคงถูกคูณกันรอบวงกลมและเครื่องหมายของผลคูณเป็นสิ่งสำคัญ อย่างไรก็ตาม ยังมีอีกสองวิธีในการจัดการกับป้ายกำกับขอบที่ไม่สอดคล้องกับทฤษฎีกราฟแบบมีเครื่องหมาย

คำว่า"กราฟที่มีเครื่องหมาย"บางครั้งใช้กับกราฟที่แต่ละขอบมีน้ำหนักw ( e ) = +1 หรือ −1 กราฟเหล่านี้ไม่ใช่กราฟที่มีเครื่องหมายแบบเดียวกัน แต่เป็นกราฟถ่วงน้ำหนักที่มีชุดน้ำหนักที่จำกัด ความแตกต่างคือ น้ำหนักจะถูกบวกเข้าด้วยกัน ไม่ใช่คูณกัน ปัญหาและวิธีการจึงแตกต่างกันอย่างสิ้นเชิง

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

ในบทความนี้ เราจะกล่าวถึงเฉพาะทฤษฎีกราฟแบบมีเครื่องหมายในความหมายที่เคร่งครัดเท่านั้น สำหรับกราฟที่มีการระบายสีตามเครื่องหมาย โปรดดูที่ เมทริก ซ์ สี

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

กราฟระบุทิศทางแบบมีเครื่องหมายไม่ควรสับสนกับกราฟระบุทิศทางแบบมีเครื่องหมายกราฟระบุทิศทางแบบมีเครื่องหมายเป็นกราฟสองทิศทางไม่ใช่กราฟระบุทิศทาง (ยกเว้นในกรณีง่ายๆ ที่เครื่องหมายทั้งหมดเป็นบวก)

กราฟที่มีเครื่องหมายที่จุดยอดบางครั้งเรียกว่ากราฟที่มีเครื่องหมายคือกราฟที่มีเครื่องหมายกำหนดให้กับจุดยอด วงกลมเรียกว่าสอดคล้อง (แต่ไม่เกี่ยวข้องกับความสอดคล้องเชิงตรรกะ) หรือกลมกลืนหากผลคูณของเครื่องหมายที่จุดยอดเป็นบวก และไม่สอดคล้องหรือไม่กลมกลืนหากผลคูณเป็นลบ ไม่มีลักษณะเฉพาะที่ง่ายของกราฟที่มีเครื่องหมายที่จุดยอดที่กลมกลืนกันในลักษณะเดียวกับทฤษฎีบทสมดุลของ Harary แต่ลักษณะเฉพาะนี้เป็นปัญหาที่ยากลำบาก ซึ่งได้รับการแก้ไขได้ดีที่สุด (โดยทั่วไป) โดย Joglekar, Shah และ Diwan (2012) ^{[ 11 ]}

โดยทั่วไปแล้ว การเพิ่มเครื่องหมายที่ขอบลงในทฤษฎีเครื่องหมายที่จุดยอดนั้นทำได้ง่ายโดยไม่ต้องเปลี่ยนแปลงอะไรมาก ดังนั้น ผลลัพธ์หลายอย่างสำหรับกราฟที่มีเครื่องหมายที่จุดยอด (หรือ "กราฟที่มีเครื่องหมายกำกับ") จึงสามารถขยายไปสู่กราฟที่มีเครื่องหมายที่จุดยอดและขอบได้อย่างเป็นธรรมชาติ โดยเฉพาะอย่างยิ่งในกรณีของการจำแนกลักษณะของความกลมกลืนโดย Joglekar, Shah และ Diwan (2012)

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

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

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

เมื่อจำกัดป้ายกำกับจุดยอดให้เป็นเซตของจำนวนเต็มที่มีขนาดไม่เกินจำนวนธรรมชาติkเซตของการระบายสีที่เหมาะสมของกราฟที่มีเครื่องหมายจะเป็นเซตจำกัด ความสัมพันธ์ระหว่างจำนวนการระบายสีที่เหมาะสมดังกล่าวกับkเป็นพหุนามในkเมื่อแสดงในรูปของ พหุนาม นี้จะเรียกว่าพหุนามสีของกราฟที่มีเครื่องหมาย ซึ่งคล้ายคลึงกับพหุนามสีของกราฟที่ไม่มีเครื่องหมาย ${\displaystyle 2k+1}$

ในจิตวิทยาสังคมกราฟแบบมีเครื่องหมายถูกใช้เพื่อจำลองสถานการณ์ทางสังคม โดยเส้นเชื่อมบวกแสดงถึงมิตรภาพ และเส้นเชื่อมลบแสดงถึงความเป็นศัตรูระหว่างโหนด ซึ่งแทนบุคคล^{[ 3 ]}ตัวอย่างเช่น วงจร 3 วงบวก คือ เพื่อนร่วมกัน 3 คน หรือ เพื่อน 2 คน ที่มีศัตรูร่วมกัน ในขณะที่วงจร 3 วงลบ คือ ศัตรูร่วมกัน 3 คน หรือ ศัตรู 2 คน ที่มีเพื่อนร่วมกัน ตามทฤษฎีความสมดุลวงจรบวกมีความสมดุลและถือเป็นสถานการณ์ทางสังคมที่มั่นคง ในขณะที่วงจรลบไม่สมดุลและถือเป็นสถานการณ์ที่ไม่มั่นคง ตามทฤษฎี ในกรณีของศัตรูร่วมกัน 3 คน เป็นเพราะการมีศัตรูร่วมกันมีแนวโน้มที่จะทำให้ศัตรู 2 คน กลายเป็นเพื่อนกันในกรณีของศัตรู 2 คน ที่มีเพื่อนร่วมกัน เพื่อนร่วมกันนั้นมีแนวโน้มที่จะเลือกคนใดคนหนึ่งมากกว่าอีกคน และเปลี่ยนมิตรภาพของคนใดคนหนึ่งให้กลายเป็นศัตรู

Antal, Krapivsky และ Reder พิจารณาพลวัตทางสังคมเป็นการเปลี่ยนแปลงเครื่องหมายบนขอบของกราฟที่มีเครื่องหมาย^{[ 12 ]}ความสัมพันธ์ทางสังคมกับเพื่อนเก่าของคู่รักที่หย่าร้างกันถูกนำมาใช้เพื่อแสดงให้เห็นถึงวิวัฒนาการของกราฟที่มีเครื่องหมายในสังคม ตัวอย่างอีกประการหนึ่งอธิบายถึงการเปลี่ยนแปลงพันธมิตรระหว่างประเทศระหว่างมหาอำนาจยุโรปในช่วงหลายทศวรรษก่อนสงครามโลกครั้งที่หนึ่งพวกเขาพิจารณาพลวัตของไตรแอดท้องถิ่นและพลวัตของไตรแอดที่ถูกจำกัด โดยในกรณีหลัง การเปลี่ยนแปลงความสัมพันธ์จะเกิดขึ้นก็ต่อเมื่อจำนวนไตรแอดที่ไม่สมดุลทั้งหมดลดลง การจำลองสันนิษฐานว่ามีกราฟที่สมบูรณ์ที่มีความสัมพันธ์แบบสุ่มโดยมีไตรแอดที่ไม่สมดุลแบบสุ่มที่เลือกสำหรับการเปลี่ยนแปลง วิวัฒนาการของกราฟที่มีเครื่องหมายที่มี โหนด Nภายใต้กระบวนการนี้ได้รับการศึกษาและจำลองเพื่ออธิบายความหนาแน่นคงที่ของลิงก์ที่เป็นมิตร

ทฤษฎีสมดุลถูกท้าทายอย่างหนัก โดยเฉพาะอย่างยิ่งในการนำไปใช้กับระบบขนาดใหญ่ บนพื้นฐานทางทฤษฎีที่ว่าความสัมพันธ์ที่เป็นมิตรจะผูกมัดสังคมเข้าด้วยกัน ในขณะที่สังคมที่แบ่งออกเป็นสองฝ่ายที่เป็นศัตรูกันจะมีความไม่เสถียรอย่างมาก^{[ 13 ]} การศึกษาเชิงทดลองยังให้การยืนยันที่อ่อนแอต่อการคาดการณ์ของทฤษฎีสมดุลเชิงโครงสร้างอีกด้วย^{[ 14 ]}

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

การใช้วิธีวิเคราะห์ที่พัฒนาขึ้นครั้งแรกในชีววิทยาประชากรและนิเวศวิทยา แต่ปัจจุบันใช้ในสาขาวิทยาศาสตร์หลายสาขา ไดกราฟแบบมีเครื่องหมายได้ถูกนำมาประยุกต์ใช้ในการให้เหตุผลเกี่ยวกับพฤติกรรมของระบบเชิงสาเหตุที่ซับซ้อน^{[ 15 ] [ 16 ]} การวิเคราะห์ดังกล่าวตอบคำถามเกี่ยวกับผลตอบรับที่ระดับต่างๆ ของระบบ และเกี่ยวกับทิศทางของการตอบสนองของตัวแปรเมื่อมีการรบกวนระบบที่จุดหนึ่งจุดหรือมากกว่า ความสัมพันธ์ของตัวแปรเมื่อมีการรบกวนดังกล่าว การกระจายความแปรปรวนทั่วทั้งระบบ และความไวหรือไม่ไวต่อการรบกวนของระบบของตัวแปรเฉพาะ

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

สมองสามารถพิจารณาได้ว่าเป็นกราฟที่มีเครื่องหมาย โดยที่การซิงโครไนซ์และการแอนตี้ซิงโครไนซ์ระหว่างรูปแบบกิจกรรมของบริเวณสมองจะกำหนดขอบบวกและลบ ในแง่นี้ ความเสถียรและพลังงานของเครือข่ายสมองสามารถสำรวจได้^{[ 17 ]}นอกจากนี้ เมื่อไม่นานมานี้ แนวคิดเรื่องความขัดแย้งได้ถูกนำมาใช้ในการวิเคราะห์เครือข่ายสมองเพื่อระบุการประกอบกันที่ไม่ธรรมดาของการเชื่อมต่อประสาทและเน้นองค์ประกอบที่ปรับได้ของสมอง^{[ 18 ]}

กราฟที่มีเครื่องหมายเป็นกราฟกำไร ชนิดพิเศษ ที่กลุ่มกำไรมีลำดับ 2 คู่ ( G , B (Σ)) ที่กำหนดโดยกราฟที่มีเครื่องหมาย Σ เป็น กราฟไบแอสชนิดพิเศษกลุ่มเครื่องหมายมีคุณสมบัติพิเศษที่ไม่พบในกลุ่มกำไรขนาดใหญ่กว่า คือ เครื่องหมายของขอบจะถูกกำหนดจนถึงการสลับโดยเซตB (Σ) ของวงจรสมดุล^{[ 19 ]}