ในทฤษฎีกราฟกราฟผสมG = ( V , E , A )คือกราฟที่ประกอบด้วยเซตของจุดยอดVเซตของขอบ ( ^แบบ ไม่มีทิศทาง) Eและเซตของขอบ (หรือส่วนโค้ง) แบบ มีทิศทางA ^{[ 1} ]

พิจารณาจุดยอดที่อยู่ติดกันขอบที่มี ทิศทาง เรียกว่าส่วนโค้งคือ ขอบที่มีทิศทางและสามารถแสดงด้วยหรือ(โปรดทราบว่าคือ หาง และคือ หัวของส่วนโค้ง) ^{[ 2 ]}นอกจากนี้ขอบที่ไม่มีทิศทางหรือขอบที่ ไม่มี ทิศทาง คือ ขอบที่ไม่มีทิศทางและสามารถแสดงด้วยหรือ^{[ 2 ]}${\displaystyle u,v\in V}$${\displaystyle {\overrightarrow {uv}}}$${\displaystyle (u,v)}$${\displaystyle u}$${\displaystyle v}$${\displaystyle uv}$${\displaystyle [u,v]}$

สำหรับตัวอย่างนี้ เราจะไม่พิจารณาลูปหรือขอบหลายเส้นของกราฟแบบผสม

เส้นทางเดินในกราฟผสม คือลำดับของจุดยอดและขอบ/ส่วนโค้ง โดยที่สำหรับทุกดัชนีจะเป็นขอบของกราฟหรือเป็นส่วนโค้งของกราฟ เส้นทางเดินนี้เรียกว่าเส้นทาง (path)หากไม่มีขอบ ส่วนโค้ง หรือจุดยอดซ้ำกัน ยกเว้นอาจจะเป็นจุดยอดแรกและจุดยอดสุดท้าย เส้นทางเดินจะเรียกว่าเส้นทางปิด (closed)หากจุดยอดแรกและจุดยอดสุดท้ายเหมือนกัน และเส้นทางปิดเรียกว่าวัฏจักร (cycle ) กราฟผสมจะเรียกว่า กราฟไร้วัฏจักร (acyclic)หากไม่มีวัฏจักรอยู่ภายใน ${\displaystyle v_{0},c_{1},v_{1},c_{2},v_{2},\dots ,c_{k},v_{k}}$${\displaystyle i}$${\displaystyle c_{i}=v_{i}v_{i+1}}$${\displaystyle c_{i}={\overrightarrow {v_{i}v_{i+1}}}}$

การระบายสีกราฟแบบผสมสามารถคิดได้ว่าเป็นการติดป้ายหรือการกำหนด สีที่แตกต่างกัน kสี (โดยที่kเป็นจำนวนเต็มบวก) ให้กับจุดยอดของกราฟแบบผสม^{[ 3 ]}จะต้องกำหนดสีที่แตกต่างกันให้กับจุดยอดที่เชื่อมต่อกันด้วยขอบ สีอาจแทนด้วยตัวเลขตั้งแต่1ถึงkและสำหรับส่วนโค้งแบบมีทิศทาง ปลายส่วนโค้งจะต้องมีสีที่เล็กกว่าหัวส่วนโค้ง^{[ 3 ]}

ตัวอย่างเช่น พิจารณาภาพทางด้านขวา สี k ที่เรามีให้เลือก สำหรับระบายสีกราฟผสมของเราคือ{1, 2, 3}เนื่องจากuและvเชื่อมต่อกันด้วยขอบ จึงต้องได้รับสีหรือป้ายกำกับที่แตกต่างกัน ( uและvมีป้ายกำกับ 1 และ 2 ตามลำดับ) นอกจากนี้เรายังมีส่วนโค้งจากvไปยังwเนื่องจากทิศทางกำหนดลำดับ เราจึงต้องกำหนดป้ายกำกับให้กับส่วนท้าย ( v ) ด้วยสีที่เล็กกว่า (หรือจำนวนเต็มจากเซตของเรา) กว่าส่วนหัว ( w ) ของส่วนโค้ง

การระบายสีkที่เหมาะสม (อย่างเข้มแข็ง)ของกราฟผสมคือฟังก์ชันc  : V → [ k ]โดยที่[ k ] := {1, 2, …, k }ซึ่งc ( u ) ≠ c ( v )ถ้าuv ∈ Eและc ( u ) < c ( v )ถ้า. ^{[ 1 ]}${\displaystyle {\overrightarrow {uv}}\in A}$

เงื่อนไขที่อ่อนกว่าบนส่วนโค้งของเราสามารถนำมาใช้ได้ และเราสามารถพิจารณาการระบายสีkที่เหมาะสมแบบอ่อนของกราฟผสมให้เป็นฟังก์ชันc  : V → [ k ]โดยที่[ k ] := {1, 2, …, k }โดยที่c ( u ) ≠ c ( v )ถ้าuv ∈ Eและc ( u ) ≤ c ( v )ถ้า. ^{[ 1 ]} อ้างอิงกลับไปยังตัวอย่างของเรา ซึ่งหมายความว่าเราสามารถกำหนดป้ายกำกับทั้งหัวและหางของ( v , w )ด้วยจำนวนเต็มบวก 2 ได้ ${\displaystyle {\overrightarrow {uv}}\in A}$

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

วิธีการ ลบ-หดตัวสามารถใช้ในการคำนวณพหุนามสีอ่อนของกราฟผสมได้ วิธีนี้เกี่ยวข้องกับการลบ (เช่น การนำออก) ขอบหรือส่วนโค้ง และอาจรวมจุดยอดที่เหลืออยู่ซึ่งเชื่อมต่อกับขอบหรือส่วนโค้งนั้นเพื่อสร้างจุดยอดเดียว^{[ 4 ]}หลังจากลบขอบe ออก จากกราฟผสมG = ( V , E , A )เราจะได้กราฟผสม( V , E – e , A ) เราใช้สัญลักษณ์ G – eแทนการลบขอบeในทำนองเดียวกัน โดยการลบส่วนโค้งa ออก จากกราฟผสม เราจะได้( V , E , A – a ) โดยเราใช้สัญลักษณ์ G – aแทนการลบaนอกจากนี้ เรายังใช้สัญลักษณ์G / eและG / aแทน การหดตัวของ eและaตามลำดับ จากข้อเสนอที่ให้ไว้ใน Beck et al. ^{[ 4 ]}เราจะได้สมการต่อไปนี้เพื่อคำนวณพหุนามสีของกราฟผสม: ^{[ 5 ]}

1. ${\displaystyle \chi _{G}(k)=\chi _{Ge}(k)-\chi _{G/e}(k)}$,
2. ${\displaystyle \chi _{G}(k)=\chi _{Ga}(k)+\chi _{G/a}(k)-\chi _{G_{a}}(k)}$.

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

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

ระบบถนนหรือทางหลวงอาจแสดงได้ด้วยเส้นเชื่อมและจุดเชื่อมต่อแบบผสม โดยเส้นเชื่อมแบบมีทิศทางแสดงถึงถนนเดินรถทางเดียวและเส้นเชื่อมแบบไม่มีทิศทางแสดงถึงถนนเดินรถสองทาง

• ไวส์สไตน์, เอริค ดับเบิลยู. "กราฟผสม" . MathWorld .