Boyama sayfası yolu. Yol boyama (matematiksel) Şehir içi toplu taşıma araçlarında ve otobüs duraklarında çocuklar için davranış kurallarını içeren boyama sayfaları

Site güncellemesi
10.12.2006 15:46
Araba ve çizgi film hayranları için - çizgi film Arabalardan boyama sayfaları.

Disney ve Pixar sayesinde, Haziran 2006'da tüm dünya sadece arabaların kahraman olduğu bir çizgi film gördü.

Arabalar ("Arabalar") çizgi filmindeki arabalar sıradan hayatlar yaşıyor - biri bir lastik dükkanı, diğeri bir tuning stüdyosu tutuyor ve bazıları hippi Fillmore (Volkswagen T1) veya eski bir arkadaşı gibi sadece kendi zevkleri için yaşıyor Dünya Savaşı Serge (Willys). "Yıldırım" lakaplı resmin ana karakteri McQueen, sadece yarış, zafer ve zafer hayal ediyor. Ünlü US Highway 66'daki Radyatör Bölgesi'ne girdikten sonra, "yeşil" McQueen herkese ne kadar hızlı ve havalı olduğunu hemen söyler. Ancak, NASCAR yarışındaki ilk start onun hayallerini dağıtır. Arkadaşlar kahramanın kayıptan kurtulmasına yardım eder - eski Meiter çekici (GMC Pick-up), akıl hocası Doc Hudson (Hudson Hornet) ve gerçek bir Ferrari görmeyi hayal eden küçük Luigi (Fiat 600).

Peki, romantik güzellik Sally olmadan (büyüleyici 911 dövmeli Porsche)! Büyük ölçüde onlar sayesinde, McQueen ana rakibi Chico'yu (Plymouth Hemi Cuda) yenerek yarışı kazanmaya devam edecek. Luigi'nin rüyası da gerçekleşecek - bir gün "Maranello'dan bir aygır" dükkanında lastikleri değiştirmek için arayacak, bu arada "Kızıl Baron" Michael Schumacher'in kendisi tarafından seslendirildi.

Hem resmin yaratıcılarının hem de seslendirenlerin arabalarla ilgili insanlar olması dikkat çekicidir. Örneğin, yönetmen Joe Lasseter, çocukluğunun çoğunu babasının baş tasarımcılardan biri olduğu Chevrolet fabrikasında geçirdi. Ford endişesinin önde gelen tasarımcısı Jay Mays, danışman olarak görev yaptı. Daha önce bahsedilen yedi kez Formula 1 dünya şampiyonu Michael Schumacher'e ek olarak, NASCAR yıldızları Richard Petty ve Paul Newman'ın yanı sıra efsanevi yarışçı Michael Andretti de kahramanları seslendirmede yer aldı.

Yalnızca orijinal araba gürültüsü kullanıldı - örneğin, özellikle yarış bölümleri için, ses NASCAR yarışmaları sırasında birkaç hafta boyunca Amerikan ovallerinde kaydedildi. Bütçesi 70 milyon USD olan resmin oluşturulması iki yıldan fazla sürdü. Bu süre zarfında 43 bin farklı araba çizimi yapıldı ve her çizim 17 saatten fazla sürdü. Filmde yeni Porsche'ler ve Ferrari'lerden antika Ford T'lere kadar toplam 120 araba karakteri var.

Çocuğun Yol Kuralları hakkındaki bilgisi, sokakta güvenliğinin ana koşullarından biridir. Yetişkinler de dahil olmak üzere birçok yaya, genellikle çeşitli şiddetlerde trafik kazalarının nedeni haline gelen bu kurallara uyma konusunda oldukça anlamsızdır. Çocuklar, köyde sokakta olmanın, yolun tam katılımcıları olduklarını, bu nedenle trafik kurallarına uymanın onların sorumluluğunda olduğunu açıkça anlamalıdır.

Boyama sayfaları Çocuklar için yolun kuralları.

Bir çocuğa sokakta (yollar, kaldırımlar, şehir içi ulaşım) davranış kurallarını öğretmeye, kendi başına yürümeyi ve koşmayı öğrenmeden önce çok erken yaşta başlanmalıdır. Ve burada çocuğun sokakta birlikte olduğu ebeveynler ve diğer yetişkinlerin örneği çok önemlidir. Çocuğunuza sadece yolun kurallarını anlatmak ve açıklamakla kalmamalı, aynı zamanda onlara kesinlikle uymalısınız. Bu sayfadaki trafik kuralları boyama sayfaları öncelikle okul öncesi çocuklara yöneliktir ve çocukların yolda ve yakınında davranışların temellerini öğrenmelerine yardımcı olacaktır.

1. Trafik ışığı boyama sayfası.

Yolu güvenli bir şekilde geçmek için en iyi yer, trafik ışıklarıyla donatılmış bir yaya geçididir. Trafik ışığı boyama sayfaları, çocukların onu kullanma kurallarını daha kolay hatırlamalarına yardımcı olmak için küçük tekerlemeler de içerir.

• Her zaman sadece trafik ışığı yeşil olduğunda sürmeye başlayın.
• Yakınlarda hiç araç olmasa bile asla kırmızı veya sarı trafik ışıklarında karşıdan karşıya geçmeyin.
• Yeşil ışığı yaktığınızda, ayrıca güvende olduğunuzdan emin olun - önce sola, sonra sağa bakın.

2. Yaya geçidinin renklendirilmesi.

Çocuğunuza anayolu sadece yaya geçidinde geçmeyi öğretin. Yaya geçitlerinin boyama sayfaları çocuklara yolu doğru bir şekilde geçmeyi öğretecektir. Trafik ışığı ile donatılmamış bir geçişe düzensiz denir.

• Yaya geçidi, yolun yüzeyinde bir zebra ile işaretlenmiştir.
• Karşıdan karşıya geçmeden önce dikkatlice inceleyin, yakınlarda trafik olmadığından emin olun.
• Karşıdan karşıya geçme, karşıya geçme.
• Karşıdan karşıya geçme.
• Görüşünüzü engelleyen duran araçlara özellikle dikkat edin.
• Yaya geçidinden geçerken telefonla konuşmayı bırakın.
• Yakınlarda yeraltı veya yüksek geçitler varsa, bunları kullandığınızdan emin olun, bu tür yerlerde trafik özellikle yoğundur.

3. Kaldırımlar.

Kaldırım yaya trafiği için tasarlanmıştır. Çocukları, özellikle yoğun trafiğin olduğu alanlarda bulunan kaldırımlarda doğru davranmaya teşvik edin.

• Yol boyunca kaldırımda sürerken, ona çok yaklaşmayın.
• Arabaların bahçelerden, sokaklardan olası çıkışını dikkatlice gözlemleyin.
• Kaldırımda top oynamayın, koşmayın.

4. Şehir içi toplu taşıma araçlarında ve otobüs duraklarında çocuklar için davranış kurallarını içeren boyama sayfaları.

Bu boyama sayfaları çocuklara toplu taşımanın güvenli kullanım kurallarını öğretecek.

• Bir toplu taşıma durağı, yolun olası görünürlüğünün düşük olması ve bir çocuğu yanlışlıkla kaldırımdan yola itebilecek büyük insan kalabalığı nedeniyle tehlikeli bir yerdir. Burada özellikle dikkatli olmanız gerekir.
• Taşımanın kapılarına ancak tamamen durduktan sonra yaklaşın.
• Araçtan indikten sonra, ancak araç duraktan ayrıldıktan sonra karşıdan karşıya geçin.

Yolun bu temel kurallarına ek olarak, çocuklar trafik işaretlerini renklendirmeye ilgi duyacaklar. Trafik kurallarına göre sunulan boyama sayfaları, küçük çocuklar, okul öncesi ve ilkokul öğrencilerinin yanı sıra anaokullarında ve ilkokuldaki derslerde kullanım için uygundur. Yolun Kurallarına sahip tüm resimler tamamen ücretsizdir - indirilebilir ve yazdırılabilirler.

Onları kum havuzunda arabalarla oynamaya davet ederseniz, çocukları uzun süre meşgul edebilirsiniz. Ama ya dışarısı soğuksa, çocuk sıkılır. Bu durumda aşağıdaki araba yolu şablonlarını indirebilir ve yazdırabilirsiniz. Tüm halkaları, dönüşleri ve düz yolları keserek eğlence başlayacak. Bu şablonlardan, bir çocuk herhangi bir şekilde bir yol oluşturabilir, sadece gerekli sayıda A4 sayfanın yazdırıldığından emin olun.

Arabalar için düz yol indir

Bu sayfalara en çok ihtiyaç duyulacak. A4 formatında bir sayfaya, yazdırılması ve kesilmesi gereken 3 yol yerleştirdik. Çocuğunuza, bölümü ihtiyaç duyduğu uzunlukta yapmak için yolu nasıl dik açılarla keseceğini gösterin.

Arabalar için yol: halka

Yolları bağlamak için şablonu yukarıda sunulan bir yüzüğe ihtiyacınız olacak ve altyapınızı ondan oluşturmaya başlayacaksınız.

Araba Yolu: Düz Dönüş

Sunulan dönüşler, çocuğun yolu ihtiyaç duyduğu yönde 90 derece döndürmesine izin verecektir.

Arabalar için yolun keskin bir dönüşü değil

Aşağıdaki A4 şablonu, yolun herhangi bir yarıçap altında dönmesine yardımcı olacaktır.

(bu giriş matematik bilgisi olan ve sempatizanları olan okuyucuların ilgisini çekebilir)

Geçen gün grafik teorisinden ilginç bir problem hakkında okudum - yol boyama varsayımı. Bu varsayım 37 yıldır açıktı, ancak üç yıl önce İsrailli matematikçi Abraham Trachtman tarafından kanıtlandı. Kanıtın oldukça basit olduğu ortaya çıktı ve bazı zorluklarla (çünkü beynim köreldi) onu okuyup anlayabildim ve hatta bu girişte açıklamaya çalışacağım.

Sorun bir örnekle açıklanabilir. Her kavşakta kuzey, güney, doğu ve batı olmak üzere dört yönden birine gidebileceğiniz bir şehir haritası hayal edin. Araba bir kavşakta başlar ve bazı yön listesini takip ederse - "kuzey, kuzey, doğu" vb. - o zaman sonunda başka bir kavşağa varacak. Nerede başladığına bakılmaksızın, arabayı aynı yere götürecek, belki de uzun bir yol tarifi listesi bulmak mümkün müdür? Harita Manhattan'a benziyorsa - normal bir ızgara - o zaman hayır, ama belki birçok çıkmaz ve beklenmedik dönüşler var?

Veya başka bir örnek. Arkadaşınız, merkezi bulmanız gereken bir labirentte sıkışıp kaldı ve sizi arayıp yardım istedi. Labirentin nasıl çalıştığını biliyorsun ama arkadaşının nerede olduğunu bilmiyorsun. Arkadaşınızı nerede olursa olsun kesinlikle merkeze götürecek bir komut dizisi olabilir mi?

Bu iki örnekte, her noktadaki "yönler" sabittir ve çözüm ya vardır ya da yoktur. Ancak daha genel bir durumda, bu problem şunu sorar: örneğin "batı, kuzey, doğu, güney" noktalarının her kesişme noktasında kendi yolunda nerede olduğunu seçebilirsek, o zaman "eşzamanlı bir kelimenin varlığını sağlayabilir miyiz?" " - herhangi bir yerden sabit bir komuta yol açacak bir dizi komut?

Genel durumda, köşeler arasında "ok" kenarları olan yönlendirilmiş bir G grafiği olsun. Bu grafiğin tek tip bir giden d derecesine sahip olmasına izin verin - bu, her köşeden tam olarak d kenarın çıktığı anlamına gelir. Aynı zamanda, her bir köşe noktasına mutlaka d olması gerekmeyen farklı bir sayı girebilir. Diyelim ki elimizde "çiçekler" diyeceğimiz bir alfabenin d harfi var. Daha sonra, grafiğin "renklendirilmesi", her köşe için, giden kenarlarının d'si için tüm d harfleri atanarak verilir. Dolayısıyla, bir tepe noktasında "yer alıyorsak" ve α rengine göre bir yere "gitmek" istiyorsak, renklendirme bize her zaman hangi yeni tepe noktasına gitmemiz gerektiğini söyleyecektir. Bir "kelime", herhangi bir harf-renk dizisidir. Daha sonra, grafikte bir renklendirme verilmişse ve x bir köşe, w bir kelime ise, xw, x'ten başlayarak ve w kelimesinden sonra ulaşacağımız köşeyi ifade eder.

boyama kitabı denir senkronizasyon, herhangi bir x köşesini tek bir sabit x 0 köşesine götüren bir w kelimesi varsa . Bu durumda w denir kelimeyi senkronize et. Yol renklendirme probleminin sorduğu soru şudur: Her zaman eşzamanlı bir renklendirme var mıdır? Bir grafiğin kenarlarını, tüm köşeleri bire indirgenebilecek şekilde renklendirmek her zaman mümkün müdür?

Bu sorunun, örneğin Wikipedia'da okunabilecek birkaç farklı alanda uygulamaları vardır. Örneğin, bilgisayar biliminde, otomata teorisinde. Renklendirmeye sahip bir grafik, köşelerin durumlar olduğu ve kenarların aralarında nasıl gezinileceğini gösterdiği deterministik bir sonlu durum makinesi olarak düşünülebilir. Diyelim ki bu otomatı uzaktan kontrol ediyoruz, bazı bilgi kanalları üzerinden komutlar gönderiyoruz ve bazı arızalar nedeniyle bu kanal kirlendi, otomat bazı hatalı talimatlar aldı ve şimdi ne durumda olduğunu bilmiyoruz. Ardından, bir sync word varsa, şimdi nerede olursa olsun, onu bilinen bir duruma getirebiliriz.

Peki senkron renklendirme ne zaman var olur? Yol renklendirme varsayımı, grafiğe iki kısıtlama daha getirir (her köşenin tam olarak d kenarı olması gerçeğinin yanı sıra). İlk olarak, grafik güçlü bir şekilde bağlı olmalıdır, bu da herhangi bir tepe noktasından diğerine bir yol olduğu anlamına gelir. İkincisi, grafik periyodik olmamalıdır. Tüm grafik köşelerinin V 1 , V 2 , ... V n kümelerine bölünebileceğini, böylece grafiğin herhangi bir kenarının bazı V i ve V i+1 veya V n ve V 0 'dan köşeleri birleştirebileceğini hayal edin. Her V'deki köşeler arasında kenar yoktur ve herhangi bir V arasında da yalnızca sırayla "atlayamazlar". Böyle bir grafiğe periyodik denir. Böyle bir grafiğin senkronize bir renklendirmeye sahip olamayacağı açıktır, çünkü nasıl renklendirirseniz ve hangi sözcükleri kullanırsanız kullanın, farklı V i'deki iki köşe asla bir araya gelmeyecektir - döngünün etrafında döneceklerdir.

Yol renklendirme teoremi, bu koşulların yeterli olduğunu söylüyor: her tepe noktasından d kenarlı, periyodik olmayan, güçlü bir şekilde bağlı herhangi bir yönlendirilmiş grafik, senkronize bir renklendirmeye sahiptir.. İlk olarak 1970 yılında bir varsayım olarak formüle edildi ve o zamandan beri özel durumları kanıtlayan birçok kısmi sonuç var, ancak tam bir kanıt sadece 2007'de ortaya çıktı. Aşağıdakiler, neredeyse tüm kanıtın yeniden anlatımıdır (bir teknik lemma hariç).

periyodiklik

Öncelikle periyodik olmama koşulunu buna eşdeğer bir koşulla değiştirelim. Bir grafik, yalnızca ve ancak grafikteki herhangi bir döngünün uzunluğunu bölen bir N>1 sayısı varsa periyodiktir. Şunlar. Periyodik olmama şartımız, böyle bir N olmadığını veya başka bir deyişle, grafikteki tüm döngülerin uzunluklarının en büyük ortak böleninin 1 olduğunu söylemeye eşdeğerdir. senkronize renklendirme.

Periyodikliğin "herhangi bir döngünün uzunluğunun bölünebilir olduğu N>1 vardır" koşuluna eşdeğer olduğunu kanıtlamak, bir yönde önemsiz, diğerinde ise kolaydır. Bunu inançla kabul etmeye istekliyseniz, bu paragrafın geri kalanını kolayca atlayabilirsiniz; kanıtın geri kalanı için önemli değil. Grafik periyodik ise, yani. Köşeleri V 1 , V 2 , ... V n kümelerine bölmek mümkün olduğundan, böylece bir döngüde kenarların aralarında gitmesi sağlanır, o halde herhangi bir döngünün uzunluğunun n ile bölünebilmesi gerektiği açıktır, yani. yeni koşul karşılanmıştır. Bu önemsiz bir yön, ancak bizim yerimizi değiştirmek için sadece ikinci yöne ihtiyacımız var. Herhangi bir döngünün uzunluğunu bölen böyle bir N>1 olduğunu varsayalım. Grafiğimizde, kökü r noktasında olan bir yönlendirilmiş yayılan ağaç (yayılan ağaç) oluşturalım. Bu ağaçta herhangi bir x köşesine l(x) uzunluğunun kökünden başlayan bir yol vardır. Şimdi, grafikteki herhangi bir p-->q kenarı için, l(q) = l(p) + 1 (mod N) olduğunu iddia ediyoruz. Bu ifade doğruysa, bundan hemen tüm köşeleri l(x) mod N'ye göre V i kümelerine bölebileceğimiz sonucu çıkar ve grafik periyodik olacaktır. Bu ifade neden doğrudur? Eğer p-->q bir yayılan ağacın parçasıysa, bu açıktır, çünkü o zaman sadece l(q) = l(p) + 1. Durum böyle değilse, o zaman r kökünden rotaları yazarız. p,q köşeleri R p ve R q olarak. Ayrıca R r, grafikte q'dan r'ye giden rota anlamına gelsin (grafik bağlantılıdır, yani vardır). O zaman iki döngü yazabiliriz: R p p-->q R r , ve R q R r . Bu döngülerin uzunluklarının N ile bölünebilmesi koşuluna göre, toplam değerleri çıkararak ve iptal ederek, ispatlanacak olan l(p)+1 = l(q) mod N'yi elde ederiz.

İstikrarlı dostluk ve indüksiyon

G grafiğinin biraz renklendirilmesine izin verin, w kelimesi onları aynı köşeye getiriyorsa iki p,q köşesine arkadaş diyoruz: pw = qw. "Hiç karşılaşmazlarsa" p,q düşmanları diyelim. Herhangi bir w kelimesini uyguladıktan sonra arkadaş kalırlarsa, p,q kararlı arkadaşlar diyelim: pw, qw ile aynı tepe noktasına gelmeyebilir, ancak biraz daha w" sonra gelebilir. Kararlı arkadaşlar asla düşman olmazlar.

Köşeler arasındaki kararlılık ilişkisi, ilk olarak, bir denkliktir (yansımalı, simetrik ve geçişlidir) ve ikinci olarak, grafik yapısı tarafından korunur: p, q kararlı arkadaşlarsa, p, p ile bir kenarla bağlanır" , q ile q" ve bu kenarlar aynı renk, daha sonra p" ve q" da kararlı arkadaşlardır. Bu, istikrarlı arkadaşlığın olduğu anlamına gelir. uyum ve şu bölümlere ayrılabilir: köşeleri G'deki kararlı arkadaşlık denklik sınıfları olacak yeni bir G" grafiği oluşturun. G'de en az bir kararlı çift varsa, G" boyutu G'den küçük olacaktır. Ayrıca, eğer Orijinal grafikte G her köşeden d kenarlara sahiptir, o zaman G" de aynı olacaktır. Örneğin, eğer P yeni bir grafiğin tepe noktasıysa, bu orijinal p1, p2 köşelerinin denklik sınıfıdır... , ve α herhangi bir renkse, p1--α-> q1, p2---α-->q2, vb. kenarların tümü, her biri ile istikrarlı dostluk içinde olan q1, q2... köşelerine yol açar. ve bu nedenle, tüm bu kenarlar yeni bir kenar P --α-->Q olacak şekilde yeni bir Q tepe noktasında bulunur ve bu, d renklerinin her biri için böyle devam eder.

Ayrıca, eğer G periyodik değilse, o zaman G" öyledir. Çünkü - alternatif periyodiklik tanımımızı kullanırsak - G'deki herhangi bir döngü G" de bir döngüye dönüşür, yani G" deki tüm döngü uzunlukları n > 1 ile bölünebiliyorsa, o zaman aynısı G'deki tüm döngüler için de geçerlidir. Dolayısıyla G'nin periyodikliği", G'nin periyodikliğini ifade eder.

Diyelim ki G"de senkronize bir renklendirme bulmayı başardık. Artık başladığımız renklendirme yerine G'de kullanılabilir: herhangi bir kenar p-->q, kenarın yeni rengine göre yeni bir renk alacaktır. P-->Q. Biraz daha kesin olarak şunu söylemeliyiz: G" grafiğinin her bir P noktasında, tüm renklerin bazı permütasyonları ile yeni bir renk verilir π P: α rengiyle boyanmış kenar yeni bir renk alır. renk π P (α). Daha sonra orijinal G grafiğinde, P kararlılık sınıfından her p noktasında, kenarlarını yeniden renklendirmek için aynı π P permütasyonunu uygularız. G grafiğinin yeni rengi genellikle orijinal olanlarla aynı olmayan bazı yeni "dostluk", "düşmanlık" ve "istikrar" kavramlarını tanımlar. Ancak yine de, eğer iki p, q köşesi eski renklendirmede sabit arkadaşlarsa - aynı P sınıfına aitse - o zaman yenisinde sabit arkadaşlar olarak kalacaklar. Bunun nedeni, p,q'yu bir tepe noktasına getiren herhangi bir w dizisinin, yol boyunca p'nin her bir köşesinde π P permütasyonu kullanılarak eski renklendirmeden yeni renge "aktarılabilmesi" veya bunun tersi olmasıdır. p,q eski renklendirmede kararlı olduğundan ve "sonuna kadar" öyle kaldığından, p,q'dan ortak tepe noktasına giden yolda p n , qn köşelerinin her bir ara çifti kararlı olacaktır, yani. aynı tepe noktası Pn içinde bulunur ve bu nedenle aynı π Pn permütasyonunu alır.

Yeni renklendirme G" için senkronize oluyor, yani bazı w dizileri tüm köşeleri tek bir P köşesine getiriyor. Şimdi G'deki yeni renklendirmeye w uygularsak, tüm köşeler "P içinde" bir yerde birleşir. Yukarıda belirtildiği gibi, tüm P sınıfındaki köşeler yeni renklendirmede sabit kalır, bu da artık her şey tek bir G köşesine yakınlaşana kadar hala ayrı olan kalan köşe çiftlerini tekrar tekrar bir araya getirerek w ile devam edebileceğimiz anlamına gelir. renklendirme G için senkronize ediliyor.

Bütün bunlardan, teoremi kanıtlamak için, koşulları karşılayan herhangi bir grafikte, bir çift kararlı arkadaşın olduğu bir renklendirme olduğunu kanıtlamak yeterlidir. Çünkü o zaman G grafiğinden boyut olarak daha küçük G" grafiğine gitmek mümkündür ve aynı zamanda tüm koşulları karşılar. Endüktif argümanı kullanarak, daha küçük boyutlu grafikler için problemin zaten çözüldüğünü varsayabiliriz ve daha sonra G" için senkronize renklendirme de G için senkronize olacaktır.

Klikler ve maksimum kümeler

Grafiğin köşelerinin herhangi bir A alt kümesi ve w kelimesi için Aw, A'nın tüm köşelerinden başlayıp w kelimesini takip ederek ulaşacağımız köşeler kümesini ifade eder. Genel olarak grafiğin tüm köşelerinden başlarsak, bunu Gw ile gösteririz. Bu gösterimde, renklendirmeyi senkronize etmek, Gw'nin bir öğe kümesi olduğu bir w olduğu anlamına gelir.

A köşe kümesi bazı w için Gw biçimine sahipse ve ayrıca A'daki herhangi iki köşe düşmansa, yani. asla yakınsama, hadi A diyelim klik. Klikler vardır çünkü her zaman bir G tamsayısıyla başlayabilir, bir çift arkadaş köşe alabilir, onları birbirine bağlayan w'yi geçebilir ve köşelerin sayısını bir azaltabiliriz; sadece düşmanlar kalana veya sadece bir köşe kalana kadar bu şekilde devam edin - bu durumda da bir klik, sadece önemsiz.

A bir klik ise, o zaman herhangi bir w kelimesi için Aw da bir kliktir; bu açıktır çünkü düşmanlar düşman olarak kalır. x grafiğin herhangi bir köşesiyse, x içeren bir klik vardır. Bu, bazı A kliği olduğu gerçeğinden kaynaklanmaktadır (önceki paragrafa bakınız); p içinde bir tepe noktasıysa, o zaman p'den x'e giden bir w sözcüğü vardır, çünkü bağlı grafik; o zaman Aw, x'i içeren bir kliktir.

Tıklamalar, istikrarlı arkadaşlarla bir renklendirme olduğunu kanıtlamamıza yardımcı olacaktır - önceki bölüme göre, bu teoremi kanıtlamak için yeterlidir. Bu bölüm boyunca, eğer A ve B'de iki klik varsa, A'daki bir ve B'deki bir köşe hariç, bu iki köşedeki tüm köşelerin ortak olduğunu kanıtlayacağız. Böylece sorun, bu tür A ve B kliklerini içeren bir renklendirme bulmaya indirgenir.

Kliklerin nasıl çalıştığını daha iyi anlamak için, bir grafikteki köşelere ağırlıklar atamak yararlıdır. Her x köşesine w(x) pozitif bir ağırlık atamanın bir yolunun olduğunu gösterelim, böylece herhangi bir x köşesi için x'te kenarları olan tüm köşelerin ağırlıklarını toplayın, sonra d*w(x) elde ederiz, burada d her tepe noktasından gelen kenarların sayısıdır. Bu lineer cebirden gelir ve eğer bir özdeğerin ne olduğunu bilmiyorsanız, bu paragrafın geri kalanını atlayın ve bu tür w(x)'in inanç üzerindeki varlığını alın. Eğer M, G grafiğinin matrisi ise ((i,j hücresi), i-->j kenarı varsa 1'dir ve böyle bir kenar yoksa 0'dır), o zaman w(x), onları tanımladığım gibi, özvektörün elemanlarıdır ayrıldıözdeğer d için bu matris. d bir özdeğer olduğu için böyle bir vektörün var olduğunu biliyoruz: önemsiz bir özvektörü var sağda(1,1,....1) - bu, her köşeden tam olarak d kenarın çıkması gerçeğinden hemen çıkar.

A herhangi bir köşe kümesiyse, w(A), A'daki tüm köşelerin ağırlıklarının toplamını gösterir; ve w(G), grafikteki tüm köşelerin ağırlıklarının toplamıdır. Ek olarak, eğer s herhangi bir kelimeyse, her bir köşeyi bu köşelerle (varsa) değiştirerek, her adımda s boyunca "ters yönde" giderseniz A'dan geldiğiniz köşe kümesini As -1 göstersin. uygun renkte ona gidin.

Şimdi bir noktada bir araya getirilebilecek tüm köşe kümelerini ele alalım, yani. Öyle ki, bazı w için Aw yalnızca bir köşe içerir. Bunların arasında w(A) maksimum ağırlığına sahip olan A kümelerine maksimal kümeler denir. Renklendirme senkronize ise, G grafiğinin tamamı bir maksimal kümedir (benzersiz), ancak aksi halde değildir.

A herhangi bir köşe kümesiyse, α'nın tüm d renklerinden geçtiği tüm w(Aα -1) toplamı d*w(A)'ya eşittir - bu yalnızca birinden ana ağırlık özelliğinin genelleştirilmesidir. A köşeleri kümesine tepe noktası. Ayrıca, A maksimum küme ise, o zaman w(Aα -1)'in her biri w(A)'dan büyük olamaz, çünkü bu kümeler de bir tepe noktasına yakınsar. Ve bu ağırlıkların toplamı d*w(A)'ya eşit olduğundan, her birinin w(A)'ya eşit olduğu ve tüm bu kümelerin de maksimal olduğu ortaya çıkıyor. Bu, eğer A maksimal ise, o zaman Aw -1'in herhangi bir w kelimesi için de maksimal olduğu anlamına gelir.

Maksimal kümeler, ayrık örnekleri grafiğin tamamını kapsayabileceğinden kullanışlıdır. Hadi kanıtlayalım.

Çiftler halinde kesişmeyen ve aynı w kelimesi ile tek a 1 ...a n köşelerine indirgenmiş bir maksimum A 1 ...A n kümemiz olsun (ilk durumda n=1 olacaktır ve sadece bir set, bu yüzden başlaması kolay). Tüm a 1 ...a n'nin birbirinden farklı olduğu açıktır, çünkü aksi takdirde maksimum kümeyi aynı son tepe noktasına sahip diğerinin öğeleriyle daha da genişletmek mümkün olurdu. Tüm A i'nin birlikte henüz G'nin tüm köşelerini tüketmediğini ve x'in tüm A i'nin dışında bir köşe olmasına izin verin. Grafik bağlantılı olduğundan, 1'den x'e bir h yolu vardır. Sonra n maksimal küme A i h -1 w -1 whw kelimesiyle a 1 ...a n son köşelerine gider ve A 1 maksimal kümesi bazı köşelere gider Awhw = (Aw)hw = (a 1 h)w = xw. Bu xw köşesi tüm a 1 ...a n 'den farklı olmalıdır, çünkü aksi takdirde maksimum A i kümesi x öğesiyle tamamlanabilir. Ve tüm bu n + 1 kümeleri - tüm A i h -1 w -1 artı A 1 - whw boyunca farklı köşelere gittiği için, hepsi ikili olarak ayrıktır. Bu genişlemeye kümenin dışında köşe kalmayana kadar devam edeceğiz.

Böylece tüm G grafiğini ayrık maksimal kümelerle kaplayabiliriz. Maksimal olduklarından, hepsinin toplamı aynı wmax'a sahiptir ve dolayısıyla kapsamadaki sayıları Nmax = w(G)/w max'tır.

Şimdi ikili düşmanlardan oluşan herhangi bir A kümesini düşünün. Örneğin, bir klik böyle bir kümenin bir örneğidir (ve ayrıca Gw biçimindedir). Maksimum setin içinde bir çift düşman olamaz, çünkü o zaman birleşemezdi. Bu nedenle, N maksimal kümelerden oluşan bir kaplamada, her biri A'nın en fazla bir üyesini içerir, dolayısıyla A'nın boyutu en fazla N maks. Özellikle, bu herhangi bir kliğin boyutu için bir üst sınırdır.

A, w'nin bir kelime olduğu Gw formunun bir kliği olsun. O zaman G = Aw -1 ve buna göre w(G), w(aw -1) toplamına eşittir, burada a, A'nın tüm köşelerinden geçer. Bir önceki paragrafa göre terim sayısı en fazla N max'tır. , ve her aw -1 kümesi bir noktaya (w kelimesiyle a noktasına) indirgenebilir, bu nedenle ağırlığı maksimum wmax değerinden büyük değildir. Toplam toplam w(G) = N max *w max olduğundan, terim sayısının tam olarak Nmax olduğu ve her terimin tam olarak wmax olduğu sonucuna varırız. Tüm tıklamaların aynı boyutta olduğunu kanıtladık: tam olarak N maksimum öğe.

İki klik A ve B olsun, öyle ki A'nın içindeki tüm öğeler, biri hariç, B ile ortak olsun: |A| - |A∩B| = 1.

A ve B aynı boyuta sahip olduğu için |B| - |A∩B| = 1, yani A ve B'nin A'daki bir p köşesi ve B'deki bir q köşesi dışında tüm unsurları ortaktır. Bu p,q köşelerinin kararlı arkadaşlar olduğunu kanıtlamak istiyoruz. Durum böyle değilse, o zaman bazı w kelimeleri onları düşman yapar, yani. pw ve qw düşmandır. Yukarıda gösterildiği gibi, Aw ve Bw de kliklerdir ve yine pw ve qw düşmanları dışında tüm ortak unsurlara sahip oldukları açıktır. O halde Aw ∪ Bw kümesi ikili düşmanlar kümesidir. Gerçekten de, Aw'nin tüm unsurları ikili düşmanlardır, çünkü o bir kliktir; aynısı Bw elemanları için de geçerlidir; ve sadece birkaç pw, qw kaldı - ayrıca düşmanlar. Ancak bu kümenin N maks +1 öğesi vardır ve yukarıda, herhangi bir ikili düşman kümesinin N maks. öğesinden fazla öğeye sahip olamayacağını gösterdik. Bu bir çelişkidir ve bu nedenle pw ve qw herhangi bir w için düşman olamaz. Başka bir deyişle, p ve q sabit arkadaşlardır.

Yayılan grafikler ve klikler

Verilen bir G grafiğinden tüm köşeleri alalım ve her köşeden yalnızca bir giden kenar seçelim. Böyle bir seçim, bizim dediğimiz bir alt grafiği tanımlar. yayılan grafik(yayılma grafiği). Pek çok farklı yayılma grafiği olabilir, ancak nasıl göründükleri hakkında biraz düşünelim. Bir yayılan grafik R olsun. İçinde herhangi bir x köşesi alıp kenarlarını izlemeye başlarsak, o zaman her seferinde tek seçeneğimiz olacak, çünkü R'de her köşeden sadece bir kenar çıkıyor ve er ya da geç yakın döngü. Belki bu döngü x'te kapanmayacak, ancak "daha ileri" bir yerde kapanacak - örneğin, x-->y->z-->s-->y. Sonra x'ten bu döngüye "kuyruk" yol açacaktır. Başka bir zirveden başlarsak, kesinlikle bir döngüye de geleceğiz - bu ya da başka bir döngü. R'nin herhangi bir köşesinin ya bir döngü üzerinde (birkaç tane olabilir) ya da döngüye yol açan "kuyruğun" bir parçası olduğu ortaya çıktı. Bu, R'nin şöyle göründüğü anlamına gelir: belirli sayıda döngü ve üzerlerine belirli sayıda "ters çevrilmiş" ağaç inşa edilmiştir: her ağaç başlamaz, ancak döngülerden birinde bulunan bir "kök" ile biter.

Grafiğin her köşesine atayabileceğimiz seviye, verilen kapsayan grafik R'deki döngüden uzaklığına karşılık gelir. Döngü üzerinde bulunan köşeler 0 seviyesine sahiptir ve çevrime bağlı ağaç üzerinde bulunan köşeler, ağaçlarında "kök"e olan mesafeye eşit bir seviye alır. "döngüde yatmak. Grafiğimizin bazı köşeleri maksimum L seviyesine sahiptir. Belki de genellikle 0'a eşittir - yani. ağaç yok, sadece döngüler var. Belki de sıfırdan büyüktür ve bu maksimum seviyenin köşeleri, farklı döngülere veya bire bağlı her tür farklı ağaçta bulunur.

Şu şekilde bir kapsayan R grafiği seçmek istiyoruz: maksimum seviyenin tüm köşeleri aynı ağaçta bulunur. Sezgisel olarak, bunun yapılabileceğine inanılabilir, çünkü durum böyle değilse - örneğin, farklı ağaçlara dağılmışlardır - o zaman bu maksimum x köşelerinden birini seçebilir ve R'ye bir kenar gidişi ekleyerek seviyesini artırabilir. x'e. O zaman başka bir kenarın atılması gerekecek ve başka bir şeye zarar vermeyeceği kesin değil... ama bu teknik bir konu, daha sonra anlatacağız. Sadece sezgisel olarak çok karmaşık görünmediğini söylemeye çalışıyorum.

Şimdilik, maksimum düzeyin tüm köşeleri aynı ağaçta olacak şekilde R'yi seçebileceğimizi varsayalım. Bu ağacın önemsiz olduğu varsayılır, yani. maksimum seviye L > 0. Bu varsayıma dayanarak, içinde A ve B klikleri olan, bir önceki bölümün koşulunu sağlayan bir renklendirme oluşturacağız ve bu, bu renklendirmenin sabit bir çift arkadaşı olduğunu kanıtlayacaktır.

Renklendirme aşağıdaki gibi olacaktır: bir renk α seçiyoruz ve R grafiğindeki tüm kenarları bu renkte ve G grafiğindeki diğer tüm kenarları herhangi bir şekilde başka renklerde (sadece bir tane varsa) renklendiriyoruz. renk, o zaman R, G ile çakışır, yani sorun yok). Böylece, α renginden oluşan kelimeler, ağaçları boyunca R'nin köşelerini döngülere doğru "ilerler" ve sonra onları döngüler boyunca yönlendirir. Sadece böyle kelimelere ihtiyacımız var.

x, R'deki maksimum L seviyesinin herhangi bir tepe noktası olsun ve K, x'i içeren herhangi bir klik olsun; Böyle bir kliğin var olduğunu biliyoruz. K, maksimum L seviyesinin başka bir köşesini içerebilir mi? Varsayımımıza göre, bu tür tüm köşeler x ile aynı ağaçtadır; bu, α L kelimesinin onları x ile aynı yere, yani bu ağacın döngü üzerinde uzanan köküne götürdüğü anlamına gelir. Dolayısıyla, bu tür tüm köşeler x'in arkadaşlarıdır ve bu nedenle onunla aynı klikte bulunamazlar. Bu nedenle, x dışında K, yalnızca alt düzey köşeleri içerebilir.

A = Kα L-1 kümesine bakalım. Bu aynı zamanda bir kliktir ve içinde x hariç tüm köşeler R'deki bazı döngülerine ulaşmıştır, çünkü x hariç A'nın tüm köşeleri L'den daha düşük bir seviyeye sahiptir. Sadece x hala döngünün dışındadır, döngüdeki köküne tam olarak 1 uzaklıkta. Şimdi, R'deki tüm döngü uzunluklarının katı olan bir m sayısı alalım - örneğin, tüm döngü uzunluklarının çarpımı. m'nin öyle bir özelliği vardır ki, eğer bir y köşesi R'deki bir döngüdeyse, o zaman α m kelimesi onu yerine döndürür: yα m = y. B = Aα m kliğine bakalım. A'nın x hariç tüm köşeleri döngüler üzerinde uzanır ve bu nedenle B'de orada kalır; ve sonunda sadece x döngüsüne girdi ve orada bir yere yerleşti. Bu, A ve B'nin kesişiminin, biri hariç, A'nın tüm köşelerini içerdiği anlamına gelir: |A| - |A∩B| = 1. Ancak bu, önceki bölüme göre, renklendirmemizin kanıtlanması gereken kararlı bir çifte sahip olduğu anlamına gelir.

Maksimum seviyeyi inşa etmek.

Geriye, aşikar olmayan bir maksimum L > 0 düzeyine sahip olacak ve bu düzeyin tüm köşelerinin aynı ağaçta uzanacak şekilde bir kapsayan R grafiğini seçmenin her zaman mümkün olduğunu kanıtlamak kalıyor.

Bu ispatın bir kısmı, okuduğum ve test ettiğim oldukça sıkıcı ve teknik bir lemma, ama tekrar etmeyeceğim, ilgilenenler için makalenin neresinde olduğunu söyleyeceğim. Ama size bu lemmaya nasıl ulaşacağınızı anlatacağım.

G grafiğine uygulayabileceğimiz iki kısıtlamaya ihtiyacımız olacak. İlk olarak, G'de döngü olmadığını söylüyoruz, yani. bir tepe noktasından aynı tepe noktasına kenarlar. Mesele şu ki, eğer grafikte bir döngü varsa, o zaman senkronize renklendirmeyi başka bir şekilde bulmak çok kolay. Bu döngüyü biraz α rengiyle renklendirelim ve sonra bu tepe noktasından "oklara karşı" zıt yönde hareket ederek, α rengi her zaman bu tepe noktasına gidecek şekilde kenarları renklendireceğiz. Grafik bağlı olduğu için, bunu düzenlemek kolaydır ve daha sonra döngü, α'nın bir gücünün tüm grafiği bu tepe noktasına getirmesini sağlar.

Sonra, bir an için, bir p tepe noktasından tüm d kenarlarının aynı q tepe noktasına çıktığını varsayalım. Buna koşullar izin veriyor, ancak bu durumda bu kenar kümesini arayacağız. demet. İkinci kısıtlamamız şudur: Farklı p ve q köşelerinden iki bağlantının götürdüğü bir r köşesi yoktur. Neden empoze edebiliriz? Çünkü p ve q'dan r'ye bağlantılar varsa, o zaman herhangi bir renklendirme için p,q ilk renkten sonra r köşesine yakınsar ve bu nedenle onlar kararlı arkadaşlardır. Yani bu durumda, yayılan grafiklerin ve kliklerin tüm inşasına ihtiyacımız yok, hemen kararlı arkadaşlar ediniyoruz. Bu nedenle, durumun böyle olmadığını varsayabiliriz.

Son olarak, tüm köşelerin döngüler üzerinde yer almadığı, ancak bazı önemsiz ağaçların bulunduğu bir kapsayan R grafiğinin her zaman var olduğunu kanıtlayalım. Bir miktar R seçiyoruz ve içindeki tüm köşelerin döngüler üzerinde olduğunu varsayalım. G grafiğinde tüm kenarlar demetler halinde yatıyorsa - yani. her zaman bir tepe noktasından çıkan tüm d kenarlar aynı tepe noktasına yol açar - o zaman R'yi seçmek her demetten sadece bir kenar seçmeyi içerir. Bu durumda, R'de yalnızca bir döngü olabilir (sonuçta, R'deki birkaç döngü, bağlantılı bir G grafiğinde birbirine bağlanamaz - G'nin tüm kenarları, yalnızca R'nin kenarlarıyla aynı köşeleri bağlar, çünkü bunlar bağlardır - ve G bağlantılı olduğundan, bu imkansızdır) ve G'deki herhangi bir döngü basitçe bu döngünün bağlantılarından diğer kenarları seçer, ama aslında bu aynı döngüdür, aynı uzunluktadır. Ancak bu, G'deki tüm döngülerin uzunluklarının bu uzunlukla bölünebilir olduğu anlamına gelir, bu da G'nin periyodik olmamasıyla çelişir. Bu nedenle, G'de tüm kenarların bağ üzerinde uzanması olamaz, yani iki p kenarı vardır. -- >q R'de ve p-->s R dışında (p'den bazı kenarların yalnızca yayılma grafiğinde yer almadığını, aynı zamanda başka bir s köşesine de yol açtığını kanıtlamak için bağlaçlar hakkında uzun bir tartışmaya ihtiyacımız vardı). Sonra p-->q yerine p-->s koyarız ve bu döngüyü "kırar" ve içinde önemsiz olmayan bir kuyruk yaratır. Bu kuyruk bize yeni grafikte önemsiz olmayan bir ağaç verecektir.

Şimdi, önemsiz olmayan ağaçları olan tüm kapsayan R grafiklerinden, döngülerde maksimum köşe sayısına sahip olan bazı R'leri seçebiliriz. T.e. döngülerde köşeleri yoktur, ancak bu sınırlamanın dışında, döngülerdeki köşe sayısı maksimize edilmiştir. Bu grafiğin bazı maksimum L düzeyinde köşeleri vardır ve bunların farklı köklere giden ağaçlar üzerinde olduğunu varsayabiliriz, aksi takdirde ihtiyacımız olanı zaten elde etmiş oluruz. Böyle bir x köşesi seçiyoruz. Grafiği, bu köşenin ağaçta L'den daha uzun olan daha uzun bir rotanın parçası olacağı ve ağaçların geri kalanının değişmeyeceği şekilde değiştirmek istiyoruz ve o zaman maksimum seviye sadece bir ağaçta olacak, ki bu bizim yaptığımız şeydir. istek. Grafiği üç şekilde değiştirebilirsiniz:

a) y-->x kenarını alın ve R'ye ekleyin ve orada bulunan y-->z kenarını atın;
b) x'ten kendi döngüsüne (döngüde r) giden yolda sadece sonuncu olan b-->r kenarını alın ve atın ve başka bir b-->z ekleyin.
c) döngünün bir parçası olan c-->r kenarını alın ve atın ve başka bir c-->z ekleyin.

Trachtman'ın makalesinin 7. Lemma'sı, bu değişikliklerden birinin (veya bazı durumlarda ikisinin) istenen sonuca yol açtığını ayrıntılı olarak kanıtlamaktadır. İşlem, hem R'nin maksimumluğunu kullanır (eğer bazı değişiklikler döngülerde R'den daha fazla sayıda köşesi olan bir grafiğe yol açarsa, bu onun maksimumluğuyla çelişir) ve yukarıda tanımlanan, iki bağlacının götürdüğü bir tepe noktası olmaması koşulunu kullanır. Sonuç olarak, her durumda, maksimum seviyenin tüm köşelerinin önemsiz olmayan bir ağaç üzerinde bulunduğu bir R grafiği elde ederiz.

Güncelleme, bir hafta sonra: yine de, bu girişi tamamen kendi kendine yeterli kılmaya ve önceki paragrafta atıfta bulunduğum lemmanın kanıtını yeniden anlatmaya karar verdim. Bunu bir diyagramla yapmak daha iyi olurdu, ancak onu çizmek veya makaleden koparmak istemiyorum, bu yüzden kelimelerle deneyeceğim. Öyleyse, önemsiz olmayan ağaçları olan bir kapsayan R grafiğimiz olduğunu ve içindeki tüm bu tür grafiklerin maksimum köşe sayısının döngülerde olduğunu düşünelim. R'yi, maksimum düzeydeki tüm köşelerin aynı ağaç üzerinde bulunduğu bir yayılma grafiğine dönüştürmeyi amaçlıyoruz; deneme sürecinde böyle bir grafiği alır almaz hemen bitiriyoruz (ve döngülerdeki köşe sayısı açısından maksimum grafiğin kaybolması umurumuzda değil, kendi içinde bizim için önemli değil, sadece süreçte kullanıyoruz). x maksimum L seviyesinin tepe noktası olsun, T üzerinde bulunduğu ağaç, r C döngüsündeki T'nin bittiği tepe noktası, b-->r x'den C döngüsüne giden yolda r'den önceki son kenar olsun. Hala bu döngüye katılan bazı ağaçların veya L düzeyinde köşeleri olan diğerlerinin olduğunu varsayabiliriz - aksi takdirde her şey zaten yapılır. Buradan, T'den L'den daha büyük bir elemana sahip bir ağaç elde etmeyi başarırsak ve bu diğer ağaçları uzatmazsak, o zaman işimiz biter.

İlk önce, yukarıdaki a) işlemini gerçekleştirmeye çalışalım: G'de biraz y-->x kenarı alın - var, çünkü grafik bağlı ve döngüler olmadan ve R'de yatmaz, çünkü x maksimum seviye. Bunu R'ye ekleyelim ve daha önce orada olan bir miktar y-->z atalım. Eğer y, T ağacı üzerinde bulunuyorsa, o zaman y-->x yeni bir çevrimi kapatır ve yeni grafikte, çevrimlerde daha fazla köşe bulunur ve hala önemsiz olmayan ağaçlar vardır (en azından R'de olan diğerleri), bu, R'nin maksimalitesiyle çelişir. Eğer y, T üzerinde yer almıyorsa ve y-->z, C döngüsünün bir parçası değilse, y-->z'yi silmek bu döngüyü bozmaz ve y-->x'i eklemek uzar. T ağacının maksimum seviyesi en az bir ve diğer ağaçlar uzamaz, bu yüzden işimiz bitti. Geriye kalan seçenek, y-->z'nin şimdi kırılmış olan C döngüsüne uzanması ve yeni bir döngünün oluşmasıdır: r'den y'ye, sonra y-->x, sonra x'den r'ye eski ağaç boyunca. Bu çevrimin uzunluğu l(ry)+1+L iken eski C çevriminin uzunluğu l(ry)+1+l(zr) idi. Yeni döngü eskisinden daha uzun olamaz, bu R'nin maksimumluğuyla çelişir, dolayısıyla L ≤ l(zr) olduğunu görüyoruz, yani. eski döngüde z'den r'ye giden yolun uzunluğu. Öte yandan, yeni grafikte, z köşesi artık en az l(zr) seviyesine sahiptir ve bu L'den büyükse, o zaman işimiz biter. Yani l(zr)=L olduğunu varsayabiliriz. Özetlemek gerekirse: a)'nın çalışmadığını varsayıyoruz ve sonra y-->z'nin C döngüsünde olduğunu biliyoruz, l(zr) = L.

Şimdi b işlemini deneyelim: b-->r kenarını başka bir b-->d kenarı ile değiştirin. Yeni köşe d'nin nerede olduğunu görelim. T ağacındaysa, önceki döngüyü bozmadan yeni bir döngü yarattık ve R'nin maksimumluğunu reddettik. Başka bir ağaçta ise, x dahil olmak üzere T'nin maksimum köşeleri şimdi L'den daha büyük bir seviyeye sahip olacak, oysa diğer ağaçlar olmayacak ve biz bittik. C değil de başka bir döngüdeyse, o zaman şimdi a) ile b) ile birlikte a): y-->z'nin C üzerinde olduğunu bildiğimiz için, bu işlem C'yi kıracaktır, ancak yeni döngüyü değil. şimdi bağlı ağaç Τ ve bu ağaç şimdi L'den daha büyük bir seviyeye sahip olacak ve tekrar işimiz bitti.

Geriye kalan seçenek, b-->d'nin de C döngüsüne r'den başka bir yerde veya aynı yerde ve sonra d=r'de bağlanmasıdır. b-->r'yi b-->d ile değiştirdikten sonra, başlangıçtaki durumla aynı durumu elde ettik - T ağacı, L seviyesindeki x düğümü, vb. - artık sadece ağaç, d tepe noktası üzerinden döngüye bağlanmıştır. Şimdi a) işlemini göz önünde bulundurarak (işe yaramadığını varsayarak) l(zd) = L olduğu sonucuna varırız, tıpkı daha önce l(zr) = L olduğu sonucuna vardığımız gibi. Ama eğer l(zd)=l(zr), yani. z'den döngü boyunca d ve r'ye olan mesafe aynıdır, o zaman bu aynı tepe noktasıdır: d=r. Dolayısıyla, eğer b) çalışmıyorsa, o zaman b'den gelen herhangi bir kenar r'ye yol açmalıdır, yani. b'den gelen kenarlar bir demet oluşturur.

Son olarak, C döngüsünde bulunan c-->r kenarını göz önünde bulundurun. b'den gelen tüm kenarların r'ye giden bağ üzerinde olduğunu varsayabileceğimiz için, yukarıda belirtilen iki bağın olamayacağı kısıtlamasını da uygulayabiliriz. bir köşe, tüm kenarlar c'den r'ye çıkmaz, ancak bir miktar c-->e kenarı vardır. c-->r'yi c-->e ile değiştirelim. Köşe e nerede olabilir? T ağacında değil, çünkü bu C döngüsünü "genişletecek" ve R'nin maksimumluğuyla çelişecek. Yani e farklı bir ağaçta veya farklı bir döngüde, hatta aynı C döngüsünde, ama r köşesinde değil. . Sonra T ağacı, döngüye bağlanmadan önce, şimdi r'den çıkan en az bir kenar ve belki daha fazla (yalnızca e, r'den hemen sonra yer alıyorsa ve c--> e, C döngüsünü tekrar kapatırsa) uzatılır, sadece r'den türetilir). Bu, x tepe noktasının ve diğer maksimal tepe noktalarının T seviyesinin artık en az L+1 olduğu ve diğer ağaçların uzamadığı ve yine ihtiyacımız olana sahip olduğumuz anlamına gelir.

Yol boyama sayfasındasınız. Bakmakta olduğunuz boyama sayfası ziyaretçilerimiz tarafından şu şekilde anlatılmaktadır "" Burada çevrimiçi olarak birçok boyama sayfası bulacaksınız. Yol boyama sayfalarını indirebilir ve ayrıca ücretsiz olarak yazdırabilirsiniz. Bildiğiniz gibi yaratıcı etkinlikler çocuğun gelişiminde büyük rol oynuyor. Zihinsel aktiviteyi harekete geçirir, estetik bir tat oluşturur ve sanat sevgisini aşılar. Yol konulu resimleri boyama süreci, ince motor becerileri, azim ve doğruluk geliştirir, çevremizdeki dünya hakkında daha fazla bilgi edinmenize yardımcı olur, sizi tüm renk ve ton çeşitleriyle tanıştırır. Her gün web sitemize, çevrimiçi renklendirebileceğiniz veya indirip yazdırabileceğiniz, erkek ve kızlar için yeni ücretsiz boyama sayfaları ekliyoruz. Kategorilere göre derlenen kullanışlı bir katalog, doğru resmi bulmayı kolaylaştıracak ve çok çeşitli boyama sayfaları, her gün boyama için yeni ve ilginç bir konu bulmanızı sağlayacaktır.