ทฤษฎีกราฟ - ตัวอย่าง

ในบทนี้เราจะกล่าวถึงตัวอย่างมาตรฐานบางส่วนเพื่อแสดงให้เห็นถึงแนวคิดที่เราได้กล่าวไปแล้วในบทก่อนหน้านี้

ตัวอย่าง 1

Find the number of spanning trees in the following graph.

วิธีการแก้

จำนวนต้นไม้ที่ทอดที่ได้จากกราฟด้านบนคือ 3 มีดังนี้ -

ทั้งสามนี้เป็นต้นไม้ที่ทอดสำหรับกราฟที่กำหนด ที่นี่กราฟ I และ II เป็นไอโซมอร์ฟิกซึ่งกันและกัน เห็นได้ชัดว่าจำนวนต้นไม้ที่ไม่มีไอโซมอร์ฟิคมีสองต้น

ตัวอย่าง 2

How many simple non-isomorphic graphs are possible with 3 vertices?

วิธีการแก้

มีกราฟที่ไม่ใช่ไอโซมอร์ฟิก 4 กราฟที่เป็นไปได้โดยมีจุดยอด 3 จุด แสดงไว้ด้านล่าง

ตัวอย่างที่ 3

Let ‘G’ be a connected planar graph with 20 vertices and the degree of each vertex is 3. Find the number of regions in the graph.

วิธีการแก้

โดยผลรวมของทฤษฎีบทองศา

20 Σผม = 1 องศา (Vi) = 2 | E |

20 (3) = 2 | E |

| E | = 30

ตามสูตรของออยเลอร์

| V | + | R | = | E | + 2

20+ | R | = 30 + 2

| R | = 12

ดังนั้นจำนวนภูมิภาคคือ 12

ตัวอย่างที่ 4

What is the chromatic number of complete graph Kn?

วิธีการแก้

ในกราฟที่สมบูรณ์จุดยอดแต่ละจุดอยู่ติดกับจุดยอดที่เหลืออยู่ (n – 1) ดังนั้นจุดยอดแต่ละจุดจึงต้องใช้สีใหม่ ดังนั้นจำนวนสี K n = n

ตัวอย่างที่ 5

What is the matching number for the following graph?

วิธีการแก้

จำนวนจุดยอด = 9

เราจับคู่จุดยอดได้ 8 จุดเท่านั้น

หมายเลขที่ตรงกันคือ 4

ตัวอย่างที่ 6

What is the line covering number of for the following graph?

วิธีการแก้

จำนวนจุดยอด = | V | = n = 7

หมายเลขครอบคลุมบรรทัด = (α 1 ) ≥ [n / 2] = 3

α 1 ≥ 3

ด้วยการใช้ 3 ขอบเราสามารถครอบคลุมจุดยอดทั้งหมด

ดังนั้นบรรทัดที่ครอบคลุมหมายเลขคือ 3