![M3 - TT - Terapan Teori Graf [PDF]](https://pdfs.asia/img/200x200/m3-tt-terapan-teori-graf.jpg)
17 0 2 MB
GRAPH PLANAR DAN PEWARNAAN GRAPH Dr. D. L. Crispina Pardede, D.E.A. Dr. Ricky Agus Tjiptanata, S.T., S.Si., M.M.
LINGKUP MATERI Penerapan Pewarnaan Simpul
Algoritma Pewarnaan Simpul Bilangan Kromatik
1
6
Graph Planar
2
5 4
3
Dual dari Graph Planar
Pewarnaan Simpul
Graph Planar Graph yang dapat digambarkan pada bidang datar tanpa ada ruas yang berpotongan
Graph Planar Bagaimana memeriksa apakah sebuah graph merupakan graph planar? A
C
B
D
Beri nama semua simpul graph
A
C
A
B
C
D
B
D
Gambar semua ruas tanpa ada yang berpotongan.
Ruas dapat digambar tanpa ada ruas yang berpotongan. Jadi, graph tersebut merupakan graph planar.
Graph Planar Beberapa jenis graph Cn: Cycle dengan n simpul Kn: Graph lengkap dengan n simpul
Apakah semua graph tersebut merupakan graph planar?
Km,n: Graph biparti lengkap dengan m+n simpul Tn: Pohon dengan n simpul Wn: Graph roda (wheel) dengan n+1 simpul
Graph Planar Cn: Cycle dengan n simpul
Cn adalah Graph Planar untuk sembarang n
Graph Planar Kn: Graph lengkap dengan n simpul
K1
K2
K3
K4
Kn adalah Graph Planar untuk n 4
K5
K6
K7
Kn bukan Graph Planar untuk n > 4
Graph Planar Km,n: Graph biparti lengkap dengan m+n simpul
K3,3
K12
K1,3
K2,2
K2,3
Tidak Planar
Km,n adalah graph planar jika tidak mengandung graph bagian K3,3
Graph Planar Tn: Pohon dengan n simpul
Tn adalah graph planar untuk sembarang n.
Graph Planar Wn : Graph roda (wheel) dengan n+1 simpul
W3
Wn adalah graph planar untuk sembarang n.
W4
Dodecahedron Sebagai Graph Planar Leonardo da Vinci (1452-1519)
Octahedron Sebagai Graph Planar Leonardo da Vinci (1452-1519)
Icosahedron Sebagai Graph Planar Leonardo da Vinci (1452-1519)
Region Pada Graph Planar Graph planar memiliki Region (daerah) yang dibatasi oleh sebuah perjalanan tertutup (cycle). REGION II REGION I
Region Pada Graph Planar Derajat Region pada graph planar ditentukan oleh panjang perjalanan tertutup yang membatasi region. REGION II REGION I
Derajat (REGION I) = 5. Derajat (REGION II) = 5.
Region Pada Graph Planar Jumlah derajat semua region pada graph planar sama dengan dua kali banyaknya ruas graph tersebut. REGION II
Jumlah ruas = 5
REGION I
Derajat (REGION I) = 5. Derajat (REGION II) = 5. Jumlah derajat region = 10
Region Pada Graph Planar Ada berapa region pada graph G = (V,E)? Hitung derajat setiap regionnya. Apakah jumlah derajat region sama dengan dua kali jumlah ruas graph? G = (V,E)
I
A
B III
II
E = 6
C
IV D
Derajat (REGION I) = 3. Derajat (REGION II) = 3. Derajat (REGION III) = 3. Derajat (REGION IV) = 3. Jumlah derajat region = 12
Formula Euler Pada Graph Planar Pada graph planar G=(V,E) berlaku n(V) - n(E) + n(R) = 2. dimana n(V) : banyaknya simpul. n(E) : banyaknya ruas. n(R) : banyaknya region.
Formula Euler Pada Graph Planar Diketahui graph planar G=(V,E). G=(V,E)
II
A
B
III
I IV
C
Jelas bahwa n(V) = 4 n(E) = 6
D
Terdapat 4 (empat) region, yaitu region I, II, III, IV. Jadi, n(R) = 4
n(V) - n(E) + n(R) = 4 – 6 + 4 = 2
Dual dari Graph Planar Graph Dual adalah dual dari graph planar. Region dari graph planar menjadi Simpul pada graph dualnya.
Dual dari Graph Planar G = (V,E)
GD = (VD, ED)
I
I B
A II III C
III
IV II D
IV
Pewarnaan Graf (Graph Coloring) Pewarnaan Graf adalah pemberian warna terhadap simpul dari graf sedemikian sehingga dua simpul yang berdampingan (atau bertetangga) mempunyai warna yang berbeda (atau tidak sama). Dikenal juga sebagai pewarnaan simpul (Vertex Coloring). Kita katakan graf G berwarna n bila graf tersebut menggunakan n warna.
C
Contoh 1:
K3 K2 A G1
G1 berwarna 1 G2 berwarna 2 G3 berwarna 3
B
A
B
A
G2 3 buah graf berbeda
G3
Pewarnaan Graf (Graph Coloring) Contoh 2:
G1 berwarna 4 G2 berwarna 3 G3 berwarna 2
3 buah graf yang sama, tetapi menggunakan jumlah warna yang berbeda
G1
G2
G3
TANTANGAN pada pewarnaan graf ini adalah Penggunaan Jumlah Warna yang paling sedikit
Bilangan Kromatik Penggunaan Jumlah Warna pada graf yang paling sedikit dikenal dengan bilangan Kromatik. Jumlah minimum warna yang dibutuhkan dalam pewarnaan graf G disebut bilangan Kromatik dari G. Ditulis dengan K(G) atau (G) Contoh 3:
K4
Graf K4 memiliki bilangan kromatik 4
Bilangan Kromatik Contoh 4:
A
A F E
A G
B
B
B F E D
C
K5
C
C D
E
K6
Graf Lengkap Kn akan memiliki bilangan kromatik n
D
K7
Bilangan Kromatik Contoh 5:
G1
G2 Graf G1 dan G2 (berupa graf Tree / Pohon) memiliki bilangan kromatik 2
Bilangan Kromatik Contoh 6:
B3,3
K3,3
Graf B3,3 merupakan Graf Bipartisi, Sedangkan Graf K3,3 merupakan Graf Bipartisi Lengkap. Keduanya memiliki bilangan kromatik 2
Bilangan Kromatik Contoh 6:
B3,3
K3,3
Graf B3,3 di atas dapat dipartisi menjadi 2, yakni partisi kiri dan partisi kanan. Sedangkan Graf K3,3 di atas dapat dipartisi menjadi 2, yakni partisi atas dan bawah Graf Bipartisi memiliki bilangan Kromatik 2
Teorema: Pernyataan berikut adalah ekivalen: (1) G Berwarna 2 (2) G adalah Bipartisi (3) Setiap sirkuit dalam G mempunyai panjang genap Teorema tersebut dapat terlihat pada contoh 5 dan 6 sebelumnya. Terlihat pula bahwa graf pohon (Tree) merupakan graf bipartisi.
Bilangan Kromatik Contoh 7:
A
A F
E
A
A G
B
H
B
B
B G F E
C
C
C F
D
C
C5
D
C6
E
D
C7
D E
C8
Graf Cycle genap akan memiliki bilangan kromatik 2, sedangkan Graf Cycle ganjil akan memiliki bilangan kromatik 3
Dalam melakukan pemberian warna simpul (sekaligus menentukan bilangan kromatik) pada pewarnaan graf, kita dapat melakukannya berdasarkan intuisi kita. Untuk graf dengan ukuran kecil (baik jumlah simpul maupun jumlah ruas nya sedikit), maka penggunaan intuisi masih dapat dilakukan dengan akurat. Sedangkan untuk graf dengan ukuran besar, kita membutuhkan langkah-langkah yang lebih jelas dan teratur. Hal ini juga diperlukan bila kita melakukannya dengan bantuan komputer. Untuk itu diperlukan suatu algoritma. Salah satu algoritma yang ada dan banyak dipergunakan adalah Algoritma Welch Powell.
Algoritma Pewarnaan Graf Algoritma Welch Powell
Secara umum, langkah-langkah algoritma Welch Powell sebagai berikut: Mula-mula kita urutkan semua simpul berdasarkan derajatnya, dari derajat besar ke derajat kecil. Ambil warna pertama, warnai simpul pertama (dalam urutan simpul tadi), kemudian simpul berikutnya yang tidak berdampingan, terus menerus, berdasarkan urutan, sampai sudah tidak bisa digunakannya warna tersebut. Kemudian kita lanjutkan dengan warna kedua, dan seterusnya, sampai semua simpul telah diberi warna.
Algoritma Pewarnaan Graf Algoritma Welch Powell
Algoritma ini memberikan cara mewarnai sebuah graf dengan memberi label simpul-simpulnya sesuai dengan urutan derajatnya.
Langkah 1 (melabel simpul sesuai dengan urutan derajatnya). Label simpul V1, V2, ..., Vn sedemikian hingga derajat (V1) ≥ derajat (V2) ≥ ... ≥ derajat (Vn). Langkah 2 (warnai simpul yang belum berwarna pertama dari urutan yang ada, dengan sebuah warna baru. Berikan warna yang belum digunakan (warna baru) pada simpul belum berwarna yang pertama dari urutan simpul yang ada. Berikan warna baru ini pada setiap simpul belum berwarna yang tidak berdampingan/bertetangga/berdekatan dengan setiap simpul yang telah diwarnai dengan warna baru tersebut. Lakukan hal itu pada semua simpul dalam urutan yang ada secara terurut, Langkah 3 (memeriksa apakah simpul grafnya telah diwarnai semua). Jika masih terdapat simpul yang belum berwarna, maka kembalilah ke langkah 2. Langkah 4 (selesai). Pewarnaan graf telah dilakukan.
Algoritma Welch Powell Contoh :
Langkah 1: Membuat urutan simpul berdasarkan derajat simpul dari besar ke kecil
A
E
B
D
C
Simpul
A
B
C
D
E
Derajat Simpul
4
3
3
3
3
Algoritma Welch Powell Contoh :
Langkah 2: Ambil Warna baru. Warnai simpul yang belum berwarna dari urutan terkiri sampai dengan terkanan, sebanyak mungkin
A
E
B
Simpul
A
B
C
D
E
Derajat Simpul
4
3
3
3
3
Warna Langkah 3: Ulangi langkah 2 bila masih ada simpul yang belum berwarna dengan menggunakan warna baru D
C
Algoritma Welch Powell Contoh :
Langkah 2: Ambil Warna baru. Warnai simpul yang belum berwarna dari urutan terkiri sampai dengan terkanan, sebanyak mungkin
A
E
B
Simpul
A
B
C
D
E
Derajat Simpul
4
3
3
3
3
Warna
W1
Langkah 3: Ulangi langkah 2 bila masih ada simpul yang belum berwarna dengan menggunakan warna baru D
C
Algoritma Welch Powell Contoh :
Langkah 2: Ambil Warna baru. Warnai simpul yang belum berwarna dari urutan terkiri sampai dengan terkanan, sebanyak mungkin
A
E
B
Simpul
A
B
C
D
E
Derajat Simpul
4
3
3
3
3
Warna
W1
W2
W2
Langkah 3: Ulangi langkah 2 bila masih ada simpul yang belum berwarna dengan menggunakan warna baru D
C
Algoritma Welch Powell Contoh :
Langkah 2: Ambil Warna baru. Warnai simpul yang belum berwarna dari urutan terkiri sampai dengan terkanan, sebanyak mungkin
A
E
B
Simpul
A
B
C
D
E
Derajat Simpul
4
3
3
3
3
Warna
W1
W2
W3
W2
W3
Langkah 3: Ulangi langkah 2 bila masih ada simpul yang belum berwarna dengan menggunakan warna baru D
C
Selesai. Diperoleh jumlah warna minimumnya adalah 3
Sebuah ketidakakuratan dalam penggunaan Algoritma Welch Powell Simpul
A H
B
A
B
C
D
E
F
G
H
Derajat Simpul 4
4
4
4
4
4
4
4
Warna G
C
F
D E
Sebuah ketidakakuratan dalam penggunaan Algoritma Welch Powell Simpul
A H
B
A
B
C
D
E
F
G
H
Derajat Simpul 4
4
4
4
4
4
4
4
Warna G
C
F
D E
W1
W1
Sebuah ketidakakuratan dalam penggunaan Algoritma Welch Powell Simpul
A H
B
A
B
C
D
E
F
G
H
Derajat Simpul 4
4
4
4
4
4
4
4
Warna G
C
F
D E
W1 W2
W1 W2
Sebuah ketidakakuratan dalam penggunaan Algoritma Welch Powell Simpul
A H
B
A
B
C
D
E
F
G
H
Derajat Simpul 4
4
4
4
4
4
4
4
Warna G
C
F
D E
W1 W2 W3 W1 W2 W3
Sebuah ketidakakuratan dalam penggunaan Algoritma Welch Powell Simpul
A H
B
A
B
C
D
E
F
G
H
Derajat Simpul 4
4
4
4
4
4
4
4
Warna G
C
F
D E
W1 W2 W3 W1 W2 W3 W4
Sebuah ketidakakuratan dalam penggunaan Algoritma Welch Powell Simpul
A H
B
A
B
C
D
E
F
G
H
Derajat Simpul 4
4
4
4
4
4
4
4
Warna G
W1 W2 W3 W1 W2 W3 W4 W5
C
F
D E
Selesai. Diperoleh jumlah warna minimumnya adalah 5
Sebuah ketidakakuratan dalam penggunaan Algoritma Welch Powell Simpul
A H
B
A
E
B
C
D
F
G
H
Derajat Simpul 4
4
4
4
4
4
4
4
W1 W1 W2 W3 W5 W2 W3 W5
Warna G
C
F
D E
Selesai. Diperoleh jumlah warna minimumnya (yang benar) adalah
4
Penerapan Pewarnaan Graf Penerapan pewarnaan Graf, yang dalam hal ini merupakan masalah penentuan bilangan bilangan kromatik dari sebuah masalah. Beberapa contoh permasalahan yang dapat diselesaikan dengan menggunakan model graf, khususnya dalam konteks penentuan bilangan kromatiknya, disajikan seperti berikut ini: -
Penjadwalan
-
Penggunaan Ruangan
-
Pewarnaan Lahan (Peta)
-
Pewarnaan Garis Permasalahan yang dapat diselesaikan dengan menggunakan pewarnaan graf adalah permasalahan yang dapat dibawa kedalam model graf, dimana setiap ruas garis yang dibentuk mencerminkan sesuatu yang tidak boleh bersamaan
Contoh Permasalahan 1: Berikut ini adalah Daftar Mahasiswa yang mengambil Mata Kuliah yang diselenggarakan pada semester ini.
Untuk Ujian Akhir Semester, Anda diminta untuk menyusun jadwal ujian tersebut. Guna meningkatkan prestasi mahasiswa, maka jadwal tersebut dibuat sedemikian sehingga setiap mahasiswa maksimal hanya mengikuti ujian 1 mata kuliah dalam 1 hari. Sedangkan untuk mempercepat proses koreksi, dialokasikan jumlah hari pelaksanaan ujian seminimal mungkin.
Langkah Penyelesaian: 1.
Buat Model Graf dari permasalahan tersebut
2.
Mencari solusi dengan menggunakan algoritma Welch Powell
1
7
2
6
3
5
Model Graf diperoleh dengan membuat simpul yang mewakili Mata Kuliah
4
Langkah Penyelesaian: 1.
Buat Model Graf dari permasalahan tersebut
2.
Mencari solusi dengan menggunakan algoritma Welch Powell
1
7
2
6
3
5
Model Graf dilanjutkan dengan membuat ruas yang mewakili Mata Kuliah yang tidak boleh dijadwalkan bersamaan waktunya (tidak boleh pada hari yang sama)
4
Langkah Penyelesaian: 1.
Buat Model Graf dari permasalahan tersebut
2.
Mencari solusi dengan menggunakan algoritma Welch Powell
1
7
2
6
3
5
Model Graf dilanjutkan dengan membuat ruas yang mewakili Mata Kuliah yang tidak boleh dijadwalkan bersamaan waktunya (tidak boleh pada hari yang sama)
4
Langkah Penyelesaian: 1.
Buat Model Graf dari permasalahan tersebut
2.
Mencari solusi dengan menggunakan algoritma Welch Powell
1
7
2
6
3
5
4
Model Graf yang diperoleh
Langkah Penyelesaian: Berikut ini tabel yang menunjukkan hubungan antara simpul, derajat simpul, dan warna. 1
7
Simpul
2
4
6
1
3
5
7
Derajat Simpul
4
4
4
3
3
3
3
2
Warna 6
Penyelesaian dengan menggunakan Algoritma Welch Powell, dimana simpul diurutkan berdasarkan derajatnya
3
5
4
Langkah Penyelesaian: Berikut ini tabel yang menunjukkan hubungan antara simpul, derajat simpul, dan warna. 1
7
Simpul
2
4
6
1
3
5
7
Derajat Simpul
4
4
4
3
3
3
3
Warna
W1 W1 W1 W2 W2 W2 W2 6
Bilangan kromatiknya 2 5 4 Jadi, banyak minimum hari berbeda yang dibutuhkan ada 2, yaitu: Hari ke-1 jadwal ujian MK 2,4,6 (SIA, PBO, SBP) Hari ke-2 jadwal ujian MK 1,3,5,7 (Graf dan Analisis Algoritma, SBD 1, IMK, Grafik Komputer)
2
3
Contoh Permasalahan 2: Ada 6 jenis zat kimia yang perlu disimpan di gudang. Beberapa pasang dari zat itu tidak dapat disimpan di tempat yang sama, karena campuran gasnya bersifat eksplosif. Untuk zat-zat semacam itu perlu dibangun ruangan-ruangan terpisah yang dilengkapi ventilasi dan penyedot udara keluar yang berlainan. Jika lebih banyak ruangan dibutuhkan, berarti lebih banyak biaya yang dikeluarkan. Karena itu perlu diketahui berapa banyak minimal ruangan yang diperlukan untuk dapat menyimpan semua zat kimia itu dengan aman. Berikut ini adalah daftar pasangan zat kimia yang tidak dapat disimpan di tempat/ruangan yang sama. Zat kimia
tidak dapat bersama dengan zat kimia
A
B, D
B
A, D, E, F
C
E
D
A, B, F
E
B, C
F
B, D
Berapa banyak minimal ruangan berbeda untuk menyimpan semua zat kimia itu secara aman?
Langkah Penyelesaian: 1.
Buat Model Graf dari permasalahan tersebut
2.
Mencari solusi dengan menggunakan algoritma Welch Powell
Zat kimia
tidak dapat bersama dengan zat kimia
A
B, D
B
A, D, E, F
C
E
D
A, B, F
E
B, C
F
B, D
Model Graf diperoleh dengan membuat simpul yang mewakili Zat Kimia
A
F
B
E
C
D
Langkah Penyelesaian: 1.
Buat Model Graf dari permasalahan tersebut
2.
Mencari solusi dengan menggunakan algoritma Welch Powell
Zat kimia
tidak dapat bersama dengan zat kimia
A
B, D
B
A, D, E, F
C
E
D
A, B, F
E
B, C
F
B, D
Model Graf dilanjutkan dengan membuat ruas yang mewakili Zat Kimia yang tidak dapat saling bersama dalam sebuah ruangan
A
F
B
E
C
D
Langkah Penyelesaian: 1.
Buat Model Graf dari permasalahan tersebut
2.
Mencari solusi dengan menggunakan algoritma Welch Powell
Zat kimia
tidak dapat bersama dengan zat kimia
A
B, D
B
A, D, E, F
C
E
D
A, B, F
E
B, C
F
B, D
A
F
B
E
C
D
Model Graf yang diperoleh
A
Berikut ini tabel yang menunjukkan hubungan antara simpul, derajat simpul, dan warna. Simpul
B
D
A
E
F
C
Derajat Simpul
4
3
2
2
2
1
F
B
E
C
Warna
Penyelesaian dengan menggunakan Algoritma Welch Powell, dimana simpul diurutkan berdasarkan derajatnya
D
A
Berikut ini tabel yang menunjukkan hubungan antara simpul, derajat simpul, dan warna. Simpul
B
D
A
E
F
C
Derajat Simpul
4
3
2
2
2
1
Warna
W1
W2
W3
W2
W3
W1
Bilangan kromatiknya 3 Jadi, banyak minimum ruang berbeda atau terpisah yang dibutuhkan ada 3, yaitu: ruangan 1 menyimpan zat B dan C ruangan 2 menyimpan zat D dan E ruangan 3 menyimpan zat A dan F
F
B
E
C
D
Contoh Permasalahan 3: Pada penggambaran peta lahan seperti di bawah ini, dikehendaki dapat terlihat jelas batas lahannya. Untuk maksud itu, maka lahan tersebut akan diberi warna. Yang diinginkan adalah penggunaan jumlah warna seminimal mungkin.
B A K
E
D C
H
G
F I
J
Langkah Penyelesaian: 1.
Buat Model Graf dari permasalahan tersebut
2.
Mencari solusi dengan menggunakan algoritma Welch Powell Model Graf diperoleh dengan membuat simpul yang mewakili Lahan B A K
E
D C
H
G
F I
J
Langkah Penyelesaian: Model Graf dilanjutkan dengan membuat ruas yang mewakili Lahan-lahan yang tidak boleh berwarna sama
B A K
E
D C
H
G
F I
J
Model Graf dari Permasalahan B A K
E
D C
H
G
F I
J
Simpul
K
E
F
B
C
D
G
H
I
A
J
Derajat Simpul
8
5
5
4
4
4
4
4
4
3
3
Warna
W1
W2
W2
W3
W3
W1
W1
W3
W3
W2
W2
Penyelesaian Model Graf menggunakan Algoritma Welch Powell, diperoleh hasil seperti di atas
B A K
E
D C
H
G
F I
J
Simpul
K
E
F
B
C
D
G
H
I
A
J
Derajat Simpul
8
5
5
4
4
4
4
4
4
3
3
Warna
W1
W2
W2
W3
W3
W1
W1
W3
W3
W2
W2
Pewarnaan yang telah dilakukan pada Model Graf sesuai hasil Algoritma Welch Powell seperti di atas
B A K
E
D C
H
G
F I
J
Proses pengembalian hasil model graf ke permasalahan semula B A K
E
D C
H
G
F I
J
Hasil Pemberian Warna Lahan B A K
E
D C
H
G
F I
J
Contoh Permasalahan 4: Berikut ini diminta untuk memberikan warna pada ruas yang ada, dimana ruas-ruas yang menempel (incidence) dengan simpul yang sama, harus memiliki warna yang berbeda.
G1
G2
G3
Pemberian warna pada ruas, merupakan bentuk pewarnaan graf yang diimplementasikan pada obyek ruas dari graf
Langkah Penyelesaian: 1.
Buat Model Graf dari permasalahan tersebut
2.
Mencari solusi dengan menggunakan algoritma Welch Powell B
Model Graf diperoleh dengan membuat simpul yang mewakili Ruas
B
E F C
A
D
G1
C
A
D
G2
A
C
B
G3
Langkah Penyelesaian:
B
Model Graf dilanjutkan dengan membuat ruas yang mewakili ruas-ruas yang tidak boleh berwarna sama
B
E F C
A
D
G1
C
A
D
G2
A
C
B
G3
Model Graf dari Permasalahan B
B
E F C
A
D
G1
C
A
D
G2
A
C
B
G3
Simpul
A
B
C
D
E
F
Derajat Simpul
4
4
4
4
4
4
Warna
W1
W2
W1
W2
W3
W3
G2 B
Penyelesaian Model Graf menggunakan Algoritma Welch Powell, diperoleh hasil seperti di atas dan di bawah
B
E F C
A
C
A
D
A
C
B
D
G1
G3
Simpul
A
B
C
D
Simpul
A
B
C
Derajat Simpul
2
2
2
2
Derajat Simpul
2
2
2
Warna
W1
W2
W1
W2
Warna
W1
W2
W3
Simpul
A
B
C
D
E
F
Derajat Simpul
4
4
4
4
4
4
Warna
W1
W2
W1
W2
W3
W3
G2 B
B
E F C
A
C
A
D
A
C
Pewarnaan yang telah dilakukan pada Model Graf sesuai hasil Algoritma Welch Powell seperti di atas dan di bawah
B
D
G1
G3
Simpul
A
B
C
D
Simpul
A
B
C
Derajat Simpul
2
2
2
2
Derajat Simpul
2
2
2
Warna
W1
W2
W1
W2
Warna
W1
W2
W3
Proses pengembalian hasil model graf ke permasalahan semula :
B
B
E F C
A
D
G1
C
A
D
G2
A
C
B
G3
Hasil Pemberian Warna Ruas
G1
G2
G3
Teorema dalam pewarnaan ruas Teorema 1 Jika G adalah graf sederhana yang derajat maksimum simpulnya adalah m, maka bilangan kromatiknya (G) adalah m (G) m+1 Hubungan antara banyaknya simpul graf lengkap dan bilangan kromatik untuk graf itu dapat dirumuskan dalam teorema berikut ini. Teorema 2 (Kn) = n, jika n ganjil dan n > 1 (Kn) = n-1, jika n genap
Teorema 3 Jika G adalah graf sederhana bipartisi yang derajat maksimum simpulnya adalah m, maka (G) = m.
Daftar Pustaka Suryadi, H.S. Teori Graf Dasar, Jakarta: Gunadarma Discrete Mathematics and Its Applications (3rd edition). Kenneth H Rosen. McGraw-Hill Inc. Singapore, 1995 L Toscano, S Stella, and E Milotti, Using graph theory for automated electric circuit solving, [tersedia: https://core.ac.uk/download/pdf/53745212.pdf] Rinaldi Munir, Diktat Kuliah Matematika Diskrit Bandung:ITB
