ทฤษฎีกราฟ - ประเภทของกราฟ

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

กราฟ Null

A graph having no edges เรียกว่ากราฟ Null

ตัวอย่าง

ในกราฟด้านบนมีจุดยอดสามจุดที่ชื่อว่า 'a', 'b' และ 'c' แต่ไม่มีขอบระหว่างพวกเขา ดังนั้นจึงเป็นกราฟ Null

กราฟเล็กน้อย

graph with only one vertex เรียกว่า Trivial Graph

ตัวอย่าง

ในกราฟที่แสดงด้านบนมีจุดยอด 'a' เพียงจุดเดียวที่ไม่มีขอบอื่น ๆ ดังนั้นมันจึงเป็นกราฟเล็กน้อย

กราฟที่ไม่ใช่ทิศทาง

กราฟที่ไม่ชี้นำมีขอบ แต่ขอบไม่ได้ชี้นำ

ตัวอย่าง

ในกราฟนี้ 'a', 'b', 'c', 'd', 'e', ​​'f', 'g' คือจุดยอดและ 'ab', 'bc', 'cd', 'da ',' ag ',' gf ',' ef 'คือขอบของกราฟ เนื่องจากเป็นกราฟแบบไม่กำหนดทิศทางขอบ "ab" และ "ba" จึงเหมือนกัน ในทำนองเดียวกันขอบอื่น ๆ ก็พิจารณาในลักษณะเดียวกัน

กราฟกำกับ

ในกราฟกำกับขอบแต่ละด้านมีทิศทาง

ตัวอย่าง

ในกราฟด้านบนเรามีจุดยอดเจ็ดจุด 'a', 'b', 'c', 'd', 'e', ​​'f' และ 'g' และแปดขอบ 'ab', 'cb', ' dc ',' ad ',' ec ',' fe ',' gf 'และ' ga ' เนื่องจากเป็นกราฟกำกับขอบแต่ละด้านจะมีเครื่องหมายลูกศรเพื่อแสดงทิศทาง โปรดทราบว่าในกราฟกำกับ "ab" จะแตกต่างจาก "ba"

กราฟอย่างง่าย

กราฟ with no loops และไม่ parallel edges เรียกว่ากราฟธรรมดา

  • จำนวนขอบสูงสุดที่เป็นไปได้ในกราฟเดียวที่มีจุดยอด 'n' คือn C 2โดยที่n C 2 = n (n - 1) / 2

  • จำนวนของกราฟที่เรียบง่ายเป็นไปได้ด้วย 'n' จุด = 2 n2 = 2 n (n-1) / 2

ตัวอย่าง

ในกราฟต่อไปนี้มีจุดยอด 3 จุดที่มี 3 ขอบซึ่งสูงสุดไม่รวมขอบขนานและลูป สามารถพิสูจน์ได้โดยใช้สูตรข้างต้น

จำนวนขอบสูงสุดที่มีจุดยอด n = 3 -

n C 2 = n (n – 1) / 2

= 3 (3–1) / 2

= 6/2

= 3 ขอบ

จำนวนกราฟอย่างง่ายสูงสุดที่มีจุดยอด n = 3 -

2 n C 2 = 2 n (n-1) / 2

= 2 3 (3-1) / 2

= 2 3

8

กราฟทั้ง 8 ดังแสดงด้านล่าง -

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

กราฟ G บอกว่าเชื่อมต่อกัน if there exists a path between every pair of vertices. ควรมีอย่างน้อยหนึ่งขอบสำหรับทุกจุดยอดในกราฟ เราจึงบอกได้ว่ามันเชื่อมต่อกับจุดยอดอื่น ๆ ที่อีกด้านหนึ่งของขอบ

ตัวอย่าง

ในกราฟต่อไปนี้จุดยอดแต่ละจุดมีขอบของตัวเองที่เชื่อมต่อกับขอบอื่น ๆ ดังนั้นจึงเป็นกราฟที่เชื่อมต่อกัน

กราฟที่ไม่ได้เชื่อมต่อ

กราฟ G ถูกตัดการเชื่อมต่อหากไม่มีจุดยอดที่เชื่อมต่ออย่างน้อยสองจุด

ตัวอย่าง 1

กราฟต่อไปนี้เป็นตัวอย่างของ Disconnected Graph ซึ่งมีองค์ประกอบสองส่วนโดยหนึ่งมีจุดยอด 'a', 'b', 'c', 'd' และอีกอันที่มี 'e', ​​'f', 'g', จุดยอด 'h'

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

ตัวอย่าง 2

ในตัวอย่างนี้มีส่วนประกอบอิสระสองส่วนคือ abfe และ cd ซึ่งไม่ได้เชื่อมต่อกัน ดังนั้นนี่คือกราฟที่ขาดการเชื่อมต่อ

กราฟปกติ

กราฟ G ถูกกล่าวว่าเป็นปกติ if all its vertices have the same degree. ในกราฟถ้าระดับของจุดยอดแต่ละจุดเป็น 'k' กราฟจะเรียกว่า 'กราฟ k-regular'

ตัวอย่าง

ในกราฟต่อไปนี้จุดยอดทั้งหมดมีองศาเดียวกัน ดังนั้นกราฟเหล่านี้จึงเรียกว่ากราฟปกติ

ในกราฟทั้งสองจุดยอดทั้งหมดมีองศา 2 เรียกว่ากราฟ 2-Regular

กราฟที่สมบูรณ์

กราฟธรรมดาที่มีจุดยอดร่วม 'n' เรียกว่ากราฟที่สมบูรณ์และเป็น denoted by ‘Kn. ในกราฟa vertex should have edges with all other verticesจากนั้นเรียกว่ากราฟที่สมบูรณ์

กล่าวอีกนัยหนึ่งถ้าจุดยอดเชื่อมต่อกับจุดยอดอื่น ๆ ทั้งหมดในกราฟจะเรียกว่ากราฟที่สมบูรณ์

ตัวอย่าง

ในกราฟต่อไปนี้จุดยอดแต่ละจุดในกราฟจะเชื่อมต่อกับจุดยอดที่เหลือทั้งหมดในกราฟยกเว้นด้วยตัวมันเอง

ในกราฟ I

ไม่ได้เชื่อมต่อ เชื่อมต่อแล้ว เชื่อมต่อแล้ว
เชื่อมต่อแล้ว ไม่ได้เชื่อมต่อ เชื่อมต่อแล้ว
เชื่อมต่อแล้ว เชื่อมต่อแล้ว ไม่ได้เชื่อมต่อ

ในกราฟ II

q s
ไม่ได้เชื่อมต่อ เชื่อมต่อแล้ว เชื่อมต่อแล้ว เชื่อมต่อแล้ว
q เชื่อมต่อแล้ว ไม่ได้เชื่อมต่อ เชื่อมต่อแล้ว เชื่อมต่อแล้ว
เชื่อมต่อแล้ว เชื่อมต่อแล้ว ไม่ได้เชื่อมต่อ เชื่อมต่อแล้ว
s เชื่อมต่อแล้ว เชื่อมต่อแล้ว เชื่อมต่อแล้ว ไม่ได้เชื่อมต่อ

กราฟวงจร

กราฟธรรมดาที่มีจุดยอด 'n' (n> = 3) และขอบ 'n' เรียกว่ากราฟวัฏจักรหากขอบทั้งหมดเป็นวัฏจักรของความยาว 'n'

หากระดับของจุดยอดแต่ละจุดในกราฟเป็นสองจะเรียกว่ากราฟวัฏจักร

Notation- C n

ตัวอย่าง

ดูกราฟต่อไปนี้ -

  • กราฟฉันมีจุดยอด 3 จุดที่มีขอบ 3 ด้านซึ่งก่อตัวเป็นวัฏจักร 'ab-bc-ca'

  • กราฟ II มีจุดยอด 4 จุดที่มีขอบ 4 จุดซึ่งก่อตัวเป็นวัฏจักร 'pq-qs-sr-rp'

  • กราฟ III มีจุดยอด 5 จุดที่มีขอบ 5 จุดซึ่งก่อตัวเป็นวัฏจักร 'ik-km-ml-lj-ji'

ดังนั้นกราฟที่กำหนดทั้งหมดจึงเป็นกราฟวัฏจักร

กราฟล้อ

กราฟวงล้อได้มาจากกราฟวัฏจักร C n-1โดยการเพิ่มจุดยอดใหม่ จุดยอดใหม่เรียกว่า aHubซึ่งเชื่อมต่อไปยังทุกจุดของ C n

สัญกรณ์ - W n

จำนวนขอบใน W n = จำนวนขอบจากฮับไปยังจุดยอดอื่น ๆ ทั้งหมด +

จำนวนขอบจากโหนดอื่น ๆ ทั้งหมดในกราฟวัฏจักรที่ไม่มีฮับ

= (n – 1) + (n – 1)

= 2 (n – 1)

ตัวอย่าง

ดูกราฟต่อไปนี้ เป็นกราฟล้อทั้งหมด

ในกราฟ I ได้มาจาก C 3โดยการเพิ่มจุดยอดที่ตรงกลางซึ่งมีชื่อว่า 'd' มันเป็นเรื่องที่แสดงเป็น W 4

จำนวนขอบใน W4 = 2 (n-1) = 2 (3) = 6

ในกราฟ II ได้มาจาก C4 โดยการเพิ่มจุดยอดที่ตรงกลางชื่อ 't' มันเป็นเรื่องที่แสดงเป็น W 5

จำนวนขอบใน W5 = 2 (n-1) = 2 (4) = 8

ในกราฟ III ได้มาจาก C 6โดยการเพิ่มจุดยอดที่ตรงกลางซึ่งมีชื่อว่า 'o' มันเป็นเรื่องที่แสดงเป็น W 7

จำนวนขอบใน W4 = 2 (n-1) = 2 (6) = 12

กราฟไซคลิก

กราฟ with at least one วงจรเรียกว่ากราฟวัฏจักร

ตัวอย่าง

ในกราฟตัวอย่างข้างต้นเรามีสองรอบ abcda และ cfgec ดังนั้นจึงเรียกว่ากราฟวัฏจักร

กราฟ Acyclic

กราฟ with no cycles เรียกว่ากราฟอะไซคลิก

ตัวอย่าง

ในกราฟตัวอย่างข้างต้นเราไม่มีรอบใด ๆ ดังนั้นจึงเป็นกราฟที่ไม่ใช่วงจร

กราฟ Bipartite

กราฟอย่างง่าย G = (V, E) ที่มีจุดยอดพาร์ติชัน V = {V 1 , V 2 } เรียกว่ากราฟสองส่วนif every edge of E joins a vertex in V1 to a vertex in V2.

โดยทั่วไปกราฟ Bipertite มีสองชุดของจุดให้เราพูด V1 และ V2 และถ้าขอบจะถูกวาดก็ควรเชื่อมต่อจุดสุดยอดใด ๆ ในชุด V 1จุดสุดยอดใด ๆ ในชุด V 2

ตัวอย่าง

ในกราฟนี้คุณสามารถสังเกตเห็นสองชุดของจุด - V 1และ V 2 ที่นี่สองขอบชื่อว่า 'AE' และ 'BD' กำลังเชื่อมต่อจุดของสองชุดวี1และวี2

ทำกราฟ Bipartite ให้สมบูรณ์

ฝ่ายกราฟ 'G' G = (V, E) กับพาร์ทิชัน V = {V 1 , V 2 } บอกว่าจะเป็นฝ่ายกราฟเสร็จสมบูรณ์หากจุดสุดยอดในทุก V 1เชื่อมต่อกับจุดสุดยอดของ V ทุก2

โดยทั่วไปฝ่ายกราฟสมบูรณ์เชื่อมต่อแต่ละจุดสุดยอดจากชุด V 1แต่ละจุดสุดยอดจากชุด V 2

ตัวอย่าง

กราฟดังต่อไปนี้เป็นฝ่ายกราฟสมบูรณ์เพราะมีขอบเชื่อมต่อแต่ละจุดสุดยอดจากชุด V 1แต่ละจุดสุดยอดจากชุด V 2

ถ้า | V 1 | = m และ | V 2 | n = แล้วฝ่ายกราฟเสร็จสมบูรณ์จะถูกแสดงโดย K m, n

  • K m, nมี (m + n) จุดยอดและ (mn) ขอบ
  • K m, nเป็นกราฟปกติถ้า m = n

โดยทั่วไปก complete bipartite graph is not a complete graph.

K m, nเป็นกราฟที่สมบูรณ์ถ้า m = n = 1

จำนวนขอบสูงสุดในกราฟสองส่วนที่มีจุดยอด n คือ -

[N 2 /4]

ถ้า n = 10, K5, 5 = [n 2/4] = [10 2 /4] = 25

ในทำนองเดียวกัน K6, 4 = 24

K7, 3 = 21

K8, 2 = 16

K9, 1 = 9

ถ้า n = 9, k5, 4 = [n2 / 4] = [92/4] = 20

ในทำนองเดียวกัน K6, 3 = 18

K7, 2 = 14

K8, 1 = 8

'G' เป็นกราฟสองส่วนถ้า 'G' ไม่มีรอบของความยาวคี่ กรณีพิเศษของกราฟสองส่วนคือกราฟดาว

สตาร์กราฟ

กราฟสองส่วนที่สมบูรณ์ของรูปแบบ K1, n-1 คือกราฟดาวที่มีจุดยอด n กราฟดาวเป็นกราฟสองส่วนที่สมบูรณ์หากจุดยอดเดียวอยู่ในชุดเดียวและจุดยอดที่เหลือทั้งหมดเป็นของอีกชุดหนึ่ง

ตัวอย่าง

ในกราฟด้านบนจากจุดยอด 'n' จุดยอด 'n – 1' ทั้งหมดเชื่อมต่อกับจุดยอดเดียว ดังนั้นจึงอยู่ในรูปของ K 1 , n-1ซึ่งเป็นกราฟดาว

ส่วนเติมเต็มของกราฟ

ให้ 'G−' เป็นกราฟธรรมดาที่มีจุดยอดบางจุดเหมือนกับ 'G' และขอบ {U, V} อยู่ใน 'G−' ถ้าไม่มีขอบใน G หมายความว่าจุดยอดสองจุดอยู่ติดกัน ใน 'G−' ถ้าจุดยอดทั้งสองไม่อยู่ติดกันใน G.

ถ้าขอบที่มีอยู่ในกราฟ I ไม่มีอยู่ในกราฟ II อื่นและถ้าทั้งกราฟ I และกราฟ II ถูกรวมเข้าด้วยกันเพื่อสร้างกราฟที่สมบูรณ์กราฟ I และกราฟ II จะถูกเรียกว่าส่วนเติมเต็มซึ่งกันและกัน

ตัวอย่าง

ในตัวอย่างต่อไปนี้กราฟ - I มีสองขอบ 'cd' และ 'bd' กราฟ -II เสริมของมันมีสี่ขอบ

โปรดทราบว่าขอบในกราฟ -I ไม่ปรากฏในกราฟ-II และในทางกลับกัน ดังนั้นการรวมกันของกราฟทั้งสองจะทำให้กราฟของจุดยอด 'n' สมบูรณ์

Note - การรวมกันของกราฟเสริมสองแบบทำให้ได้กราฟที่สมบูรณ์

ถ้า 'G' เป็นกราฟธรรมดา ๆ

| E (G) | + | E ('G -') | = | E (Kn) | โดยที่ n = จำนวนจุดยอดในกราฟ

ตัวอย่าง

ให้ 'G' เป็นกราฟธรรมดาที่มีจุดยอดเก้าจุดและขอบสิบสองด้านให้หาจำนวนขอบใน 'G-'

คุณมี | E (G) | + | E ('G -') | = | E (น) |

12 + | E ('G -') | =

9 (9-1) / 2 = 9 C 2

12 + | E ('G -') | = 36

| E ('G -') | = 24

'G' เป็นกราฟธรรมดาที่มีขอบ 40 ขอบและส่วนเสริม 'G−' มี 38 ขอบ ค้นหาจำนวนจุดยอดในกราฟ G หรือ 'G−'

ให้จำนวนจุดยอดในกราฟเป็น 'n'

เรามี, | E (G) | + | E ('G -') | = | E (น) |

40 + 38 = n (n-1) / 2

156 = n (n-1)

13 (12) = n (n-1)

n = 13