❤เซตของจุด V สามารถที่จะแยกออกเป็น 2 เซตย่อยที่ไม่มีสมาชิกร่วมกัน (disjoint
set) คือ V1 และ V2 ทุกๆ เส้นเชื่อมในกราฟจะเชื่อมต่อจุดหนึ่งใน V1 ไปยังจุดหนึ่งใน V2

นิยามที่ 5.1
Simple graph G1 = (V1, E1) และ G2 = (V2, E2) จะพ้องรูปกัน (isomorphic)
ถ้ามีฟังก์ชัน f แบบ bijection จาก V1 ไปยัง V2 ที่มีคุณสมบัติคือ

• a และ b จะเชื่อมต่อกัน (adjacent) ใน G1 ก็ต่อเมื่อ f(a) และ f(b) เชื่อมต่อกันใน
  G2 สำหรับทุก a และ b ใน V1
  
  

หรือ simple graph 2 อันจะพ้องรูปกันเมื่อ

• มีฟังก์ชันแบบ bijection ระหว่างจุดของกราฟทั้ง 2 ซึ่งยังคงมีความสัมพันธ์แบบ
  adjacent กันอยู่ด้วย

u adjacent to v และ v adjacent from u
เรียกจุด u ว่า จุดเริ่มต้น (initial vertex) ของ (u, v)

เรียก v ว่าเป็น จุดปลาย (terminal or end vertex) ของ (u, v)

ซึ่งในกรณีของ loop ทั้งจุดเริ่มต้นและจุดปลายจะเป็นจุดเดียวกัน

การพิจารณาแบบง่ายจะพิจารณาจาก

• จำนวนจุดเท่ากันหรือไม่
• จำนวนเส้นเชื่อมเท่ากันหรือไม่
• จำนวนดีกรีของแต่ละจุดเท่ากันหรือไม่
  ถ้าไม่เท่ากัน : กราฟทั้งสองไม่พ้องรูปกัน
  ถ้าเท่ากัน : ต้องพิจารณาในรายละเอียดเพิ่มเติม

นิยามที่ 5.10
สำหรับกราฟแบบมีทิศทาง

❤ตัวอย่าง จาก Simple Graph เราสามารถแบ่งให้ออกเป็น Disjoint Set ของ Vertex ได้ .. กล่าวคือ ภายในแต่ละเซต ที่ถูกแบ่ง จะไม่มี Edge ที่เชื่อมกันระหว่างสมาชิกภายในเซตกันเองเลย

❤กราฟแบบสองส่วนสมบูรณ์ (Complete Bipartite Graph)กราฟแบบสองส่วนที่แต่ละจุดใน V1 เชื่อมต่อไปยังทุกจุดใน V2
เขียนแทนด้วย Km,n

ทางเดินและการพ้องรูปกันของกราฟ

นิยามที่ 5.12
ให้ n เป็นจำนวนเต็มบวกและ G เป็นกราฟแบบไม่มีทิศทาง ทางเดินที่มีความยาว
n จากจุด u ไปยัง v ในกราฟ G คือ

• ลำดับของเส้นเชื่อมจำนวน n เส้น คือ e1, e2 , . . ., en ของ G
• ซึ่ง f(e1) = {x0, x1}, f(e2) = {x1, x2}, . . .,f(en) = {xn-1, xn} โดยที่ x0 = u และ xn =v

❤ จุด 2 จุด คือ u และ v ในกราฟแบบไม่มีทิศทาง G จะเรียกว่า adjacent (หรือ
neighbors) ถ้า {u, v} เป็นเส้นเชื่อมของ G และถ้า e = {u, v}
เส้นเชื่อม e ว่า incident กับจุด u และ v อาจกล่าวว่าเส้นเชื่อม e connect u และ v
โดยจุด u และ v จะเรียกว่าเป็น endpoints ของเส้นเชื่อม {u, v}

นิยามที่ 5.13

• ทางเดินที่เริ่มต้นและจบที่จุดเดียวกันเรียกว่า “วงจร (Circuit)”

นิยามที่ 5.14

• ทางเดินหรือวงจรจะเรียกว่าเป็น “ทางเดินแบบง่าย (Simple path) หรือวงจรแบบง่าย (Simple circuit)” เมื่อผ่านเส้นเชื่อมเดียวกันแค่ 1 ครั้งเท่านั้น

นิยามที่ 5.15

• กราฟแบบไม่มีทิศทางจะกล่าวว่า “ถูกเชื่อมต่อกัน (connected)” ถ้ามีทางเดินระหว่างทุกๆ คู่ของจุดในกราฟ

กราฟที่ไม่เชื่อมต่อกัน

• ประกอบด้วย connected subgraphs ตั้งแต่ 2 subgraphs ขึ้นไป
• แต่ละ connected subgraphs จะเรียกว่า "Connected components" ของกราฟ

❤Degree ของจุดๆ หนึ่งในกราฟแบบไม่มีทิศทาง คือ จำนวนของเส้นเชื่อมที่ต่อกับ
จุดนั้นๆ กรณี loop ที่จุดนั้นจะนับ degree เป็น 2 โดย degree ของจุด v เขียน
แทนด้วย deg (v)
จุดที่มี degree = 0 เรียกว่า "Isolated".
จุดที่มี degree = 1 เรียกว่า "Pendant".

นิยามที่ 5.20
กราฟใดๆ จะเป็นกราฟแบบระนาบ ถ้าสามารถวาดกราฟดังกล่าวโดยที่ไม่มีเส้นเชื่อมใดตัดกัน

คุณสมบัติบางประการของ K3, 3 และ K5
กราฟทั้งสองเป็นกราฟที่มีดีกรีของทุกๆ จุดในกราฟเท่ากัน
กราฟทั้งสองเป็นกราฟแบบไม่ระนาบ (Nonplanar graph)
ถ้าลบเส้นเชื่อมเส้นใดเส้นหนึ่งออกจากกราฟจะทำให้เป็นกราฟแบบระนาบได้

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

นิยามที่ 5.16
กราฟแบบมีทิศทางจะเป็น strongly connected ถ้ามีทางเดินจาก a ไป b และ
จาก b ไป a เมื่อใดก็ตามที่ a และ b เป็นจุดในกราฟ

นิยามที่ 5.17
กราฟแบบมีทิศทางจะเป็น weakly connected ถ้ามีทางเดินระหว่างทุกๆ คู่
ของจุดในกราฟ โดยไม่สนใจทิศทาง

การให้สีกราฟ คือ การกำหนดสีให้แต่ละจุดของกราฟโดย 2 จุดที่เชื่อมติดกัน
(adjacent) ต้องไม่มีสีเดียวกัน
การให้สีกราฟนั้นจะพยายามใช้สีให้น้อยที่สุด
จำนวนสีอย่างน้อยที่ต้องใช้ในการให้สีกราฟใดๆ เรียกว่า “Chromatic number
of a graph”

ลบเส้นเชื่อมแบบลูปออก
รวมเส้นเชื่อมที่ต่อแบบอนุกรมกันเป็นเส้นเชื่อมเดียว
ลบเส้นเชื่อมที่ขนานกันระหว่างคู่ของจุดออกให้เหลือเพียง 1 เส้น
ค้นหาและวาดวงจรแบบง่ายซึ่งใช้เส้นเชื่อมมากที่สุด
วาดเส้นเชื่อมและจุดที่เหลือซึ่งไม่ได้อยู่ในวงจรแบบง่ายโดยพยายามหลีกเลี่ยงการตัดกัน
ของเส้นเชื่อม
หากไม่สามารถหลีกเลี่ยงได้ก็ให้หากราฟย่อยที่คล้ายรูปกับ K5 หรือ K3, 3 เพื่อยืนยัน
ว่ากราฟดังกล่าวเป็นกราฟแบบไม่ระนาบ