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

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

กราฟ 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' คือⁿ C ₂โดยที่ⁿ C ₂ = n (n - 1) / 2
จำนวนของกราฟที่เรียบง่ายเป็นไปได้ด้วย 'n' จุด = 2 _ⁿค₂ = 2 ^{n (n-1) /} 2

ตัวอย่าง

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

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

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

= 3 (3–1) / 2

= 6/2

= 3 ขอบ

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

2 _{ⁿ C ₂} = 2 ^{n (n-1) / 2}

= 2 ^{3 (3-1) / 2}

= 2 ³

กราฟทั้ง 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 ‘K_n’. ในกราฟ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 ₃โดยการเพิ่มจุดยอดที่ตรงกลางซึ่งมีชื่อว่า 'd' มันเป็นเรื่องที่แสดงเป็น W 4

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

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

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

ในกราฟ III ได้มาจาก C ₆โดยการเพิ่มจุดยอดที่ตรงกลางซึ่งมีชื่อว่า '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 ₁ , V ₂ } เรียกว่ากราฟสองส่วนif every edge of E joins a vertex in V1 to a vertex in V₂.

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

ตัวอย่าง

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

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

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

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

ตัวอย่าง

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

ถ้า | V ₁ | = m และ | V ₂ | 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 ² /4]

ถ้า n = 10, K5, 5 = [n 2/4] = [10 ² /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 ¹ , ^n-1ซึ่งเป็นกราฟดาว

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

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

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