Matdis 205 - 212 [PDF]

Citation preview

6.3 Critical Graf Pada bagian ini kita akan mempelajari graf dengan indek kromatik k, tapi yang sangat dekat untuk mendapatkan indek terkecil. Graf ini telah terbukti bermanfaat untuk menemukan batas atas yang cocok untuk indek kromatik. Sebuah graf G disebut K-critical jika x(G) = K dan X(G-v) < k untuk setiap titik v pada G. Sehingga sebuah graf adalah k-critikal jika graf membutuhkan k warna tapi masingmasing dari titiknya dihapus subgraf dapat diwarnai dengan warna yang lebih kecil dari k. Untuk mendapatkan memamahami lebih lanjut definisi mari kita lihat graf k-kritis untuk nilai-nilai k kecil. berpikir sejenak menunjukkan bahwa Kl adalah satu-satunya graf 1-critical. Sebuah graf G bipartit akan menjadi 2-kritis (menurut Teorema 6.2) dan sedemikian rupa sehingga, untuk setiap simpul v, G - v adalah pewarnaan-1 yg berhasil, yaitu, G - v adalah sebuah graf kosong. Graf seperti itu tidak dapat memiliki lebih dari satu ujung dan dari ini kita melihat bahwa K2 adalah satu-satunya graf 2-critical. Ternyata bahwa graf 3-critical justru siklus graf ganjil C 2n+1. Karena, seperti yang kita telah mengatakan sebelumnya, tidak ada yang mudah karakterisasi k-chromatic graf ketika 𝑘 ≥ 3, maka tidak mengherankan bahwa ada sama ada deskripsi mudah graf k-kritis ketika 𝑘 ≥ 4. Gambar 6.14 menunjukkan graf 4-critical - verifikasi ini diserahkan kepada pembaca di Latihan 6.3.3 - sementara contoh lain diberikan nanti pada Gambar 6.15.



Teorema 6.6 (Dirac 1952), misalkan G adalah k-critikal graf maka a) G adalah terhubung b) Derajat dari setiap titik dari G setidaknya k-1, c) Graf G tidak memiliki pasangan dari subgrapf G1 dan G2 untuk G= G1 U G2 dan G1 n G2 adalah graf komplet. d) G-v adalah terhubung untuk setiap titik v dari G



Bukti a. Andaikan G tidak terhubung.karena  (G) = k, oleh teorema 6.1(e, ada komponen C terhubung pada G dengan  (G) = k,kemudian jika v adalah titik pada G tidak di C, C akan menjadi komponen pada subgrap G-v.oleh teorema 6.1(e)  (G - v) =  (C) = k.ini menunjukan kontradiksi dengan Gadalah k- critical.jadi G terhubung. b. Andaikan v titik pada G dengan d(v) < k-1.G adalah k-kritikal sehingga subgrap G-v memiliki (k-1) warna dan v memiliki k-2 tetangga.tetangga ini tidak digunakan semua warna pada (k-1) warna pada G-v.oleh pewarnaan v dengan satu tidak digunakan warna memperluas pewarnaan k-1 pada G-v untuk k-1 warna pada G.ini berarti kontradiksi karena  (G)=k.kemudian setiap titik v memiliki paling kecil k-1 c. Andaikan bahwa G=G1 U G2 dimana G1 dan G2 adalah subgrap dari 𝐺1 ⋂𝐺2 = Kt dan G adalah K-kritikal G1 dan G2 keduanya memiliki indeks kromatiksebanyak k-1.pilih (k1) warna untuk G1 dan satu untuk G2. Bersamaan irisan 𝐺1 ⋂𝐺2 karena di lengkapi.setiap titik memiliki warna yang berbeda (pada setiap k-1 warna).ini tidak dapat kita menyusun warna kembali di k-1 warna pada G2 karena akan memberikan warna yang sama untuk setiap titik di 𝐺1 ⋂𝐺2 sama dengan warna yang di berikan pada G1.kombinasi dua warna akan enghasilkan k-1 warna pada semua di G.ini tidak mungkin karena  (G) = k.sedemikian hingga supgraps G1,G2 ada. d. Andaikan G-v tidak terhubung untuk beberapa titik v pada G.dan G-v memiliki subgrap H1 dan H2 dengan H1 U H2 = G-v dan 𝐻1 ⋂𝐻2 = V, himpunan G1 dan G2 adalah subgraf pada G diinduksikan H1 dengan v dan H2 dengan v. Kemudian G = G1⋃G2 dan 𝐺1 ⋂𝐺2 = K1 (dengan vk titik tunggal) ini kontradiksi dengan (c) dan juga G-v tidak dapat terhubung. Kita akan menggunakan teorema 6.6 (b) untuk membuktikan hasil tentang kromatik k grapas.pertama kita tunjukan bahwa setiap kromatik k grap G terdiri k – critical subgrapas.untuk melihat ini catatan bahwa jika G tidak K- critical maka  (Gv) = k untuk beberapa titik v pada G.jika G-v terbentuk menjadi K- critical maka kita peroleh subgrap. Jika G –v tidak K-kritical mka G-{v,w} = (G-v)-w memiliki indeks kromatik k.untuk beberapa titik w pada G-v.jika subgrap baru adalah k- critical maka sebelum di selesaikan.jika tidak kita hapus titik dan terjadi k-kritical sub graf.



Teorema 6.7 misalkan G graf dengan X(G) = K. maka G memiliki setidaknya k titik v sehingga d(v) ≥k-1. Bukti Tunjukan H k-kritical subgraf pada G.kemudian setiap titik H memiliki derajat paling rendah k-1 pada H.oleh teorema 6.6(b) dan sehingga memiliki derajat paling kecil rendah Pada G juga.karena H k-kromatic memiliki titik k terkecil terpenuhi.



Teorema 6.8 misalkan G sebuah graf dan misalkan V1, v2, Vn sebuah daftar titik dari graf G sehingga d(v1)≥d(v2)≥….≥d(vn). Maka



Bukti Jika G graf kosong  (G) = 1 dan d(vi)= 0 untuk setiap i. Kemudian max {min {I,d(vi)+1}}= max {min{I,1}}=1 Sekarang dipunyai G tidak kosong dengan  (G) = k.maka G memiliki k-kritical subgrap.oleh teorema 6.7 H memiliki titik k terendah pada derajat k terendah konsekuensinya pada G.kemudian kita berikan daftar titik G kita punyai d(vi)  k-1 untuk I = 1,….,k Kususnya min {k,d(vk)+1}=k. kemudian Max {min {min{I,d(vi)+ }}   (G)



6.4 Cliques Untuk setiap graf G, sebuah subgraf complet dari G disebut clique dari G. bilangan dari titik di sebuah cliques terbesar dari G disebut bilangan clique dari G dan di notasikan oleh 𝑐𝑙(𝐺)



Contoh, dalam gambar 6.16 𝑐𝑙(𝐺1 ) = 3, 𝑐𝑙(𝐺2 ) = 4 and 𝑐𝑙(𝐺3 ) = 2 Dari Teorema 6.1 (d) bahwa untuk setiap graf G, 𝑐𝑙(𝐺) ≤ 𝑥(𝐺) Khususnya jika G berisi segitiga, yaitu, K3, sebagai subgraph, lalu 𝑥(𝐺) ≥ 3. Untuk melihat bahwa sebaliknya tidak berlaku, perhatikan bahwa jika n ≥ 2 maka siklus C2n+1 adalah segitiga bebas dengan indeks kromatik 3. Bahkan kita sekarang memberikan teorema yang menunjukkan bahwa seseorang dapat membangun graf G dengan indeks kromatik tinggi tapi klik jumlah hanya 2. Konstruksi ini disebabkan oleh Mycielski [48] Teorema 6.9 (Mycielski, 1955) untuk setiap 𝑘 ≥ 1 ada sebuah kromatik-k graf Mk dengan subgraf non segitiga. Bukti Kami menggunakan induksi pada k. Graf K1 dan K2 menunjukkan bahwa hasilnya benar untuk k = 1 dan 2 masing-masing. Sekarang anggaplah bahwa 𝑘 ≥ 2 dan 𝑀𝑘 itu adalah graf k-kromatik yang tidak mengandung segitiga. Kami menggunakan 𝑀𝑘 untuk membuat graf (k + 1) -kromatik Mk + 1 yang tidak mengandung segitiga. Pertama anggaplah bahwa v1, v2, ...., vn adalah simpul dari 𝑀𝑘 . Simpul dari graf baru 𝑀𝑘 + 1 didefinisikan sebagai simpul 𝑀𝑘 bersama dengan ekstra n + 1 titik yang dilambangkan oleh u1, u2, ..., un, v. Set tepi 𝑀𝑘+1 didefinisikan untuk terdiri dari semua tepi Mk bersama dengan ujung dari v ke masing-masing 𝑢𝑖 dan tepi dari setiap ui ke masing-masing tetangga vi. Dimulai dengan 𝑀2 = 𝐾2 , Gambar 6.17 menunjukkan konstruksi 𝑀3 dan 𝑀4 . Kami sekarang menunjukkan bahwa 𝑀𝑘+1 tidak memiliki segitiga. Anggaplah ini salah, yaitu ada segitiga di 𝑀𝑘+1 . Karena 𝑀𝑘 , dengan asumsi, tidak mengandung segitiga,



segitiga semacam itu harus memiliki v atau setidaknya satu dari 𝑢𝑖 sebagai titik. Karena tidak ada dua ui yang berdekatan dan v hanya bersebelahan dengan 𝑢𝑖 , ini memaksa segitiga menjadi bentuk 𝑣𝑗 𝑣𝑘 𝑢𝑖 𝑣𝑗 . Namun, karena ui berdekatan dengan 𝑣𝑗 dan 𝑣𝑘 , simpul yang terakhir ini haruslah tetangga 𝑣𝑖 dan kita mendapatkan segitiga 𝑣𝑗 𝑣𝑘 𝑣𝑖 𝑣𝑗 , tidak mungkin karena ini terletak pada 𝑀𝑘 . Jadi 𝑀𝑘+1 tidak memiliki segitiga, seperti yang diperlukan. Sekarang kami tunjukkan bahwa 𝑋(𝑀𝑘+1 ) ≤ 𝑘 + 1. Mengingat k-mewarnai Mk kita dapat memperpanjang ini ke (k + 1) -colouring dari 𝑀𝑘+1 dengan mewarnai masing-masing ui dengan warna yang ditetapkan untuk vi dan kemudian mewarnai v dengan warna (k + 1) st. (Ini mudah diperiksa bahwa ini adalah (k + 1) -colouring dari 𝑀𝑘+1 , karena cara menetapkan tepi 𝑀𝑘+1 didefinisikan). Jadi 𝑋(𝑀𝑘+1 ) ≤ 𝑘 + 1 dan sekarang kita harus menunjukkan bahwa 𝑀𝑘+1 tidak dapat berwarna k.



Misalkan, sebaliknya, bahwa 𝑀𝑘+1 memiliki k-pewarna menggunakan warna 1,2, ..., k. Misalkan simpul v berwarna k. Maka setiap simpul ui tidak dapat diwarnai k, karena v dan ui, bersebelahan. Juga, karena 𝑋(𝑀𝑘 ) = 𝑘, warna k harus digunakan untuk mewarnai beberapa simpul dalam 𝑀𝑘 . Ubah warna simpul-simpul tersebut menjadi berwarna 𝑀𝑘 dengan warna yang diberikan ke 𝑢𝑖 yang sesuai. Kemudian, karena 𝑢𝑖 dan 𝑣𝑖 memiliki tetangga yang sama persis dalam 𝑀𝑘 , ini telah menghasilkan (k-1) -colouring dari Mk, yang merupakan kontradiksi sejak 𝑋(𝑀𝑘 ) = 𝑘. Sekarang mengikuti bahwa 𝑋(𝑀𝑘+1 ) = 𝑘 + 1, menyelesaikan bukti. Kami mencatat bahwa graf 𝑀4 yang ditunjukkan pada Gambar 6.17 dikenal sebagai graf Grotzsch.



Meskipun konstruksi Mycielski menunjukkan bahwa secara umum bilangan clique mungkin sangat berbeda dengan indeks kromatik, ada kelas besar graf di mana jumlahnya sama. Untuk mendeskripsikan kelas ini, pertama-tama kita perlu hasil pada pelengkap 𝐺̅ dari graf G.



Teorema 6.10 G sebuah graf, kemudian dua kalimat berikut adalah equivalen. (a) Untuk setiap U subset tak kosong dari V G baik GU  subgraf induksi dari G terputus maupun G U  subgraph induksi dari G terputus (b) G tidak memiliki titik yang berakibat subgraf isomorfik ke P4, lintasan dengan panjang 3. Bukti Anggaplah bahwa ada subset U dari G sedemikian sehingga subgraf yang diinduksi G [U] dari G adalah isomorfik menjadi P4. Karena P4 adalah pelengkap sendiri, subgraf yang diinduksi 𝐺̅ [𝑈] dari 𝐺̅ juga bersifat isomorfik ke P4. Secara khusus, G [U] dan 𝐺̅ [𝑈] keduanya terhubung. Argumen ini menunjukkan bahwa (a) menyiratkan (b). Sekarang anggap bahwa G tidak mengandung subgraph isomorfik verteks-induksi ke P4. Kami mengadopsi bukti dengan kontradiksi untuk menunjukkan bahwa (a) berlaku. Dengan demikian kita mengasumsikan bahwa G memang mengandung himpunan tidak kosong U sedemikian rupa sehingga baik G[U] dan 𝐺̅ [𝑈] terhubung. Jelas kita dapat memilih subset U seperti itu untuk memiliki sejumlah kecil simpul sebanyak mungkin. Jadi jika T adalah bagian dari U yang benar maka G[T] atau 𝐺̅ [𝑇] terhubung. Juga pemikiran sesaat menunjukkan bahwa minimum subset U kami memiliki setidaknya 4 simpul. Biarkan u1 menjadi simpul dalam U dan atur U1 = U-{u1}. Kemudian, dengan minimalitas U, baik G[U1] atau G [U1] terputus. Anggap bahwa F [U1] terputus. (Itu sudah cukup untuk melakukan ini karena, setelah argumen kami selesai, kami dapat mengganti G oleh G karena P4 adalah pelengkap dari dirinya sendiri.) Kemudian, karena G[U] terhubung, ada simpul u2 di U1 seperti u1u2 ∉ E (G), set tepi G. Nyatakan set titik dari komponen G [U1] yang mengandung u2 oleh U2. Maka setiap simpul u3 di U2 tidak memiliki tetangga di set U1-U2. Selain itu, karena G [U] terhubung, ada semacam simpul u3 yang berdekatan dengan u1 dalam G dan juga sebuah simpul u4



∈ U1 - U2 juga berdampingan dengan u1 dalam G. Jadi sejauh ini kita memiliki u1u2∈E (G) dan u1u3 , u1u4∈E (G). Misalkan 𝑋 = {𝑥 ∈ 𝑈2 : 𝑥 𝑖𝑠 𝑎 𝑛𝑒𝑖𝑔ℎ𝑏𝑜𝑢𝑟 𝑜𝑓 𝑢1 𝑖𝑛 𝐺} and 𝑌 = {𝑦 ∈ 𝑈2 : 𝑦 𝑖𝑠 𝑎 𝑛𝑒𝑖𝑔ℎ𝑏𝑜𝑢𝑟 𝑜𝑓 𝑢1 𝑖𝑛 𝐺̅ }. Kemudian X dan Y sama-sama nonempty sejak u_3∈X dan u2∈Y. Juga jelas U2 = X⋃Y dan X⋂Y = v. Selain itu, karena G [U2] terhubung (dengan definisi U2 ada simpul x∈X dan y∈Y sedemikian sehingga xy∈E (G). Terakhir, beri Z = {u4, u1, x, y}. Maka kita memiliki u4 u1, u1x, xy∈E (G) tetapi u1 y∉E (G), dengan definisi Y, dan u4x, u4 y∉E (G), karena u4 tidak ada dalam komponen G [U2] dari G [U1]. Ini mengikuti bahwa G[Z] adalah isomorfik ke P4, bertentangan dengan asumsi awal kami. Jadi (b) mengimplikasikan (a), seperti yang diperlukan. Kami sekarang menggunakan Teorema 6.10 untuk membuktikan hasil akhir kami dari bagian ini. Karena Seinsche [56], ini menampilkan kelas graf di mana nomor klik tidak sama dengan indeks kromatik.



Teorema 6.11 (Seinsche, 1974) Misalkan G graph yang mana tidak terdapat himpunan dari empat titik induksi P4 sebagai sebuah subgraf. Kemudian xG  cl G . Bukti Kami menggunakan induksi pada n, jumlah simpul G. Untuk n = 1 hasilnya benar sejak X (K1) = cl (K1) = 1. Sekarang anggaplah bahwa hasilnya benar untuk semua graf yang memuaskan hipotesis dan dengan paling banyak n simpul di mana n ≥ 1 adalah tetap. Biarkan G menjadi graf dengan n + 1 simpul di mana tidak ada bagian dari empat simpul menginduksi P4 sebagai subgraph. Kemudian, oleh Theorem 6.10, untuk setiap subset nonempty U dari V (G) baik G [U] atau 𝐺̅ [𝑈] terputus. Khususnya, dengan mengambil U = V (G), kita melihat bahwa G atau pelengkap 𝐺̅ terputus. Pertama anggap bahwa G terputus dan menunjukkan komponennya oleh G1, G2, ..., Gi, sehingga t ≥ 2. Maka jelas tidak ada Gi berisi P4 sebagai subgraf yang diinduksi. Jadi, karena setiap Gi memiliki lebih sedikit simpul daripada G, asumsi induksi kami memberikan X (Gi) = cl (Gi) untuk setiap i = 1, ..., t. Karena 𝑋(𝐺) = max{𝑥(𝐺𝑖 ): 1 ≤ 𝑖 ≤



𝑡}, oleh Teorema 6.1 (e), dan 𝑐𝑙(𝐺) = max{𝑐𝑙(𝐺𝑖 ): 1 ≤ 𝑖 ≤ 𝑡} (lihat Latihan 6.4.1), dapat



diikuti bahwa X (G) = cl (G), sesuai kebutuhan. Sekarang anggap bahwa 𝐺̅ terputus dan menunjukkan pelengkap komponennya oleh H1, H2,…, Hs, sehingga s ≥ 2. Karena G tidak mengandung P4 sebagai subgraf yang diinduksi tidak melakukan masing-masing dari Hi. Jadi, sekali lagi oleh asumsi induksi kami, X (Hi) = cl (Hi) untuk i = 1, ..., s. Selain itu, dengan Latihan 1.5.5 (d), G adalah 𝐺 = 𝐻1 + 𝐻2 + ⋯ + 𝐻𝑠 Oleh karena itu, dengan Latihan 6.3.4 (a), 𝑋(𝐺) = ∑𝑠𝑖=1 𝑋(𝐻𝑖 ). Karena 𝑐𝑙(𝐺) = ∑𝑠𝑖=1 𝑋(𝐻𝑖 ) (oleh Latihan 6.4.3) maka X(G) = cl(G), sesuai kebutuhan. Hasilnya sekarang diikuti dengan induksi. Cukup mudah untuk melihat bahwa kebalikan dari Teorema 6.11 salah. Ambil saja G menjadi P4 itu sendiri.