Teori Grafik - Contoh
Dalam bab ini, kita akan membahas beberapa contoh standar untuk mendemonstrasikan konsep yang telah kita bahas di bab sebelumnya.
Contoh 1
Find the number of spanning trees in the following graph.
Larutan
Jumlah pohon merentang yang diperoleh dari grafik di atas adalah 3. Mereka adalah sebagai berikut -
Ketiganya adalah pohon rentang untuk grafik yang diberikan. Di sini grafik I dan II isomorfik satu sama lain. Jelasnya, jumlah pohon rentang non-isomorfik adalah dua.
Contoh 2
How many simple non-isomorphic graphs are possible with 3 vertices?
Larutan
Ada 4 grafik non-isomorfik yang dimungkinkan dengan 3 simpul. Mereka ditunjukkan di bawah ini.
Contoh 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.
Larutan
Dengan jumlah teorema derajat,
20 Σ i = 1 derajat (Vi) = 2 | E |
20 (3) = 2 | E |
| E | = 30
Dengan rumus Euler,
| V | + | R | = | E | + 2
20+ | R | = 30 + 2
| R | = 12
Sehingga jumlah wilayahnya ada 12.
Contoh 4
What is the chromatic number of complete graph Kn?
Larutan
Dalam graf lengkap, setiap simpul bersebelahan adalah sisa (n – 1) simpul. Karenanya, setiap simpul membutuhkan warna baru. Karenanya bilangan kromatik K n = n.
Contoh 5
What is the matching number for the following graph?
Larutan
Jumlah simpul = 9
Kita hanya bisa mencocokkan 8 simpul.
Nomor yang cocok adalah 4.
Contoh 6
What is the line covering number of for the following graph?
Larutan
Jumlah simpul = | V | = n = 7
Nomor penutup garis = (α 1 ) ≥ [n / 2] = 3
α 1 ≥ 3
Dengan menggunakan 3 sisi, kita bisa menutupi semua simpul.
Oleh karena itu, nomor penutup garis adalah 3.