ทฤษฎีกราฟ - ตัวอย่าง
ในบทนี้เราจะกล่าวถึงตัวอย่างมาตรฐานบางส่วนเพื่อแสดงให้เห็นถึงแนวคิดที่เราได้กล่าวไปแล้วในบทก่อนหน้านี้
ตัวอย่าง 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