Kolorowanka droga. Kolorowanki zasady ruchu drogowego Stabilna przyjaźń i indukcja

Aktualizacja strony internetowej
10.12.2006 15:46
Dla fanów samochodów i kreskówek - kolorowanki z kreskówki Auta.

Dzięki Disneyowi i Pixarowi w czerwcu 2006 roku cały świat zobaczył kreskówkę, w której bohaterami stały się wyłącznie samochody.

Samochody z kreskówek Auta prowadzą zwyczajne życie – jeden prowadzi sklep z oponami, inny studio tuningowe, a jeszcze inni po prostu żyją dla własnej przyjemności, jak hipis Fillmore (Volkswagen T1) czy jego przyjaciel, weteran II wojny światowej.Serge (Willysa). Główny bohater filmu, McQueen, nazywany „Błyskawicą”, marzy tylko o wyścigach, zwycięstwach i chwale. Będąc w dzielnicy Radiator District przy słynnej amerykańskiej autostradzie 66, wciąż „zielony” McQueen od razu mówi wszystkim, jaki jest szybki i fajny. Jednak jego pierwszy start w wyścigu NASCAR rozwiewa jego złudzenia. Bohaterowi pomagają przyjaciele – stara laweta Mater (GMC Pick-up), mentor Doc Hudson (Hudson Hornet) i mały Luigi (Fiat 600), który marzy o zobaczeniu prawdziwego Ferrari.

Cóż byśmy byli bez romantycznej piękności Sally (Porsche z uroczym tatuażem 911)! W dużej mierze dzięki nim McQueen nadal zwycięży w wyścigu, pokonując głównego rywala Chico (Plymouth Hemi Cuda). Spełni się także marzenie Luigiego – pewnego dnia do jego warsztatu na zmianę opon przyjedzie „ogier z Maranello”, któremu głosi zresztą sam „Czerwony Baron”, Michael Schumacher.

Warto zauważyć, że zarówno twórcy filmu, jak i ci, którzy go użyczyli, to ludzie zajmujący się samochodami. Na przykład reżyser Joe Lasseter spędził prawie całe dzieciństwo w fabryce Chevroleta, gdzie jego ojciec był jednym z głównych projektantów. Wiodący projektant Forda, Jay Mays, był konsultantem. Oprócz wspomnianego już siedmiokrotnego mistrza świata Formuły 1 Michaela Schumachera, w głosach postaci wzięli udział gwiazdy NASCAR Richard Petty i Paul Newman, a także legendarny kierowca wyścigowy Michael Andretti.

Wykorzystano jedynie oryginalne odgłosy samochodów – np. specjalnie do odcinków wyścigowych dźwięk był nagrywany przez kilka tygodni na amerykańskich owalach podczas zawodów NASCAR. Prace nad filmem, którego budżet wynosił 70 milionów dolarów, trwały ponad dwa lata. W tym czasie powstało 43 tysiące różnych szkiców samochodów, a każdy rysunek trwał ponad 17 godzin. W filmie występuje łącznie 120 postaci samochodów – od nowych Porsche i Ferrari po zabytkowego Forda T.

Znajomość Regulaminu przez dziecko ruch drogowy- jeden z głównych warunków jego bezpieczeństwa na ulicy. Wielu pieszych, w tym dorosłych, traktuje te zasady dość lekko, co często staje się przyczyną wypadków drogowych o różnej sile. Dzieci muszą jasno zrozumieć, że przebywając na ulicy w obszarze zaludnionym, są pełnoprawnymi uczestnikami ruchu drogowego, dlatego też przestrzeganie przepisów ruchu drogowego jest ich obowiązkiem.

Kolorowanki Zasady ruchu drogowego dla dzieci.

Nauczanie dziecka zasad zachowania na ulicy (drogi, chodniki, komunikacja miejska) należy rozpocząć już od samego początku młodym wieku zanim nauczy się samodzielnie chodzić i biegać. I tutaj bardzo ważny jest przykład rodziców i innych dorosłych, z którymi dziecko jest na ulicy. Musisz nie tylko opowiadać i wyjaśniać dziecku zasady ruchu drogowego, ale także sam ich ściśle przestrzegać. Prezentowane na tej stronie kolorowanki z przepisami ruchu drogowego są przeznaczone przede wszystkim dla przedszkolaków i pomogą dzieciom poznać podstawowe punkty zachowania na drodze, a także w jej pobliżu.

1. Kolorowanka Sygnalizacja świetlna.

Najlepszym miejscem bezpiecznego przejścia przez jezdnię jest przejście dla pieszych wyposażone w sygnalizację świetlną. Kolorowanki z wizerunkami sygnalizacji świetlnej zawierają także małe rymowanki, które pomagają dzieciom łatwiej zapamiętać zasady ich używania.

• Zawsze rozpoczynaj jazdę dopiero, gdy zapali się zielone światło.
• Nigdy nie przechodź przez ulicę, gdy sygnalizacja świetlna jest czerwona lub żółta, nawet jeśli w pobliżu nie ma żadnych pojazdów.
• Wchodząc na zielone światło dodatkowo zadbaj o swoje bezpieczeństwo - spójrz w lewo, potem w prawo.

2. Kolorowanka przejście dla pieszych.

Naucz swoje dziecko, aby przechodziło przez jezdnię tylko na przejściu dla pieszych. Kolorowanki z przejściami dla pieszych nauczą dzieci, jak prawidłowo przechodzić przez jezdnię. Przejście, które nie jest wyposażone w sygnalizację świetlną, nazywa się nieuregulowanym.

• Przejście dla pieszych oznaczone jest na jezdni przejściem dla pieszych.
• Przed przejściem przez jezdnię dokładnie ją sprawdź i upewnij się, że w pobliżu nie ma ruchu.
• Przejdź przez ulicę, nie biegaj po niej.
• Nie przechodź przez ulicę po przekątnej.
• Zwróć szczególną uwagę na stojące pojazdy, które zasłaniają Ci widok.
• Przechodząc przez przejście dla pieszych, przestań rozmawiać przez telefon.
• Jeśli w pobliżu znajdują się metro lub wiadukty, koniecznie z nich skorzystaj, w takich miejscach ruch jest szczególnie intensywny.

3. Chodniki.

Chodnik przeznaczony jest dla ruchu pieszego. Ucz dzieci prawidłowego zachowania na chodnikach, szczególnie tych znajdujących się w obszarach o dużym natężeniu ruchu.

• Jadąc chodnikiem wzdłuż drogi, nie zbliżaj się do niego zbyt blisko.
• Uważnie monitoruj możliwe pojazdy wyjeżdżające z dziedzińców i alejek.
• Nie graj w piłkę na chodniku ani nie biegaj.

4. Kolorowanki z zasadami zachowania dzieci w komunikacji miejskiej i na przystankach autobusowych.

Te kolorowanki nauczą dzieci, jak bezpiecznie korzystać z transportu publicznego.

• Przystanek komunikacji miejskiej jest miejscem niebezpiecznym ze względu na możliwą słabą widoczność drogi i duży tłum ludzi, którzy mogą przypadkowo zepchnąć dziecko z chodnika na jezdnię. Tutaj trzeba zachować szczególną ostrożność.
• Do drzwi pojazdu należy podchodzić dopiero po jego całkowitym zatrzymaniu.
• Po wyjściu z pojazdu przystąpić do przechodzenia przez jezdnię dopiero po opuszczeniu przez niego przystanku.

Oprócz tych podstawowych zasad ruchu drogowego dzieci będą zainteresowane kolorowaniem znaków drogowych. Prezentowane kolorowanki z przepisami ruchu drogowego są odpowiednie dla małych dzieci, przedszkolaków i uczniów szkół podstawowych, a także do wykorzystania w przedszkolach i na lekcjach w szkole podstawowej. Wszystkie zdjęcia z przepisami ruchu drogowego są całkowicie bezpłatne - można je pobrać i wydrukować.

Jesteś w kategorii kolorowanek w drodze. Kolorowanka, którą rozważasz, jest opisana przez naszych gości w następujący sposób: „” Tutaj znajdziesz wiele kolorowanek online. Możesz pobrać kolorowanki drogowe i wydrukować je za darmo. Jak wiadomo, zajęcia twórcze odgrywają ogromną rolę w rozwoju dziecka. Aktywizują aktywność umysłową, kształtują gust estetyczny i zaszczepiają miłość do sztuki. Rozwija się proces kolorowania obrazków na temat drogi umiejętności motoryczne, wytrwałość i dokładność, pomaga dowiedzieć się więcej o otaczającym nas świecie, wprowadza nas w całą różnorodność kolorów i odcieni. Codziennie dodajemy do naszej witryny nowe, bezpłatne kolorowanki dla chłopców i dziewcząt, które można pokolorować online lub pobrać i wydrukować. Wygodny katalog, uporządkowany według kategorii, ułatwi znalezienie odpowiedniego obrazka, a duży wybór kolorowanek pozwoli Ci każdego dnia znaleźć nowy, ciekawy temat do kolorowania.

Możesz zająć chłopców na długi czas, jeśli zaprosisz ich do zabawy samochodami w piaskownicy. Co jednak zrobić, gdy na zewnątrz jest zimno, a dziecko się nudzi. W takim przypadku możesz pobrać i wydrukować poniższe szablony dróg dla samochodów. Zabawę zaczniemy od wycięcia wszystkich pierścieni, zakrętów i prostych dróg. Z tych szablonów dziecko może zbudować drogę o dowolnym kształcie, wystarczy wydrukować wymaganą liczbę wymaganych arkuszy A4.

Pobierz prosta droga dla samochodów

Będziesz potrzebować większości tych arkuszy. Na kartce papieru formatu A4 umieściliśmy 3 drogi, które należy wydrukować i wyciąć. Pokaż dziecku, jak przeciąć drogę pod kątem prostym, aby uzyskać potrzebny odcinek.

Droga dla samochodów: obwodnica

Aby połączyć drogi, będziesz potrzebować pierścienia, którego wzór przedstawiono powyżej, i od niego zacznij budować swoją infrastrukturę.

Droga dla samochodów: prosty skręt

Przedstawione zakręty pozwolą chłopcu skręcić drogę pod kątem 90 stopni, w wybranym przez siebie kierunku.

Nie ostry zakręt na drodze dla samochodów

Poniższy szablon A4 pomoże Ci skręcić w dowolnym promieniu.

(ten wpis może zainteresować czytelników znających matematykę i sympatyków)

Któregoś dnia przeczytałem o ciekawym problemie z teorii grafów – hipotezie o kolorowaniu dróg. Hipoteza ta była otwarta od 37 lat, ale trzy lata temu została udowodniona przez izraelskiego matematyka Abrahama Trachtmana. Dowód okazał się dość elementarny i z pewnymi trudnościami (ponieważ mój mózg uległ zanikowi) udało mi się go przeczytać i zrozumieć, a nawet spróbuję go wyjaśnić w tym poście.

Problem można wyjaśnić na następującym przykładzie. Wyobraź sobie plan miasta, na którym na każdym skrzyżowaniu możesz jechać w jednym z czterech kierunków - na północ, południe, wschód i zachód. Jeśli samochód rusza z jakiegoś skrzyżowania i postępuje według określonej listy instrukcji - „północ, północ, wschód” itp. - wtedy w końcu dotrze do innego skrzyżowania. Czy można znaleźć listę wskazówek, możliwie długą, która doprowadzi maszynę w to samo miejsce, niezależnie od tego, gdzie się zacznie? Jeśli mapa wygląda jak Manhattan – zwykła siatka – to nie, ale może ma dużo ślepych zaułków i nieoczekiwanych zakrętów?

Albo inny przykład. Twój przyjaciel utknął w labiryncie, w którym musi znaleźć centrum, i zadzwonił do Ciebie z prośbą o pomoc. Wiesz, jak działa labirynt, ale nie wiesz, gdzie jest twój przyjaciel. Czy może istnieć sekwencja poleceń, która z pewnością przeniesie Twojego przyjaciela do centrum, gdziekolwiek się znajduje?

W tych dwóch przykładach „kierunki” w każdym punkcie są ustalone i rozwiązanie albo istnieje, albo nie. Ale bardziej ogólnie, problem ten dotyczy pytania: jeśli możemy wybrać, gdzie na przykład „zachód, północ, wschód, południe” wskazuje inaczej na każdym skrzyżowaniu, czy możemy wtedy zapewnić istnienie „słowa synchronizacji” – sekwencji poleceń, które każde miejsce doprowadzi do jednego stałego?

W ogólnym przypadku niech będzie graf skierowany G z krawędziami „strzałkowymi” pomiędzy wierzchołkami. Niech ten graf będzie miał jednakowy stopień zewnętrzny d - oznacza to, że każdy wierzchołek ma dokładnie d krawędzi. W tym przypadku można wprowadzić każdy pojedynczy wierzchołek różne ilości, opcjonalnie d. Miejmy zestaw d liter jakiegoś alfabetu, który nazwiemy „kolorami”. Następnie podaje się „kolorowanie” grafu poprzez przypisanie każdemu wierzchołkowi wszystkich d liter dla jego d wychodzących krawędzi. Jeśli więc „jesteśmy” w jakimś wierzchołku i chcemy „dojść” gdzieś zgodnie z kolorem α, to kolorowanie zawsze powie nam, do której krawędzi musimy dotrzeć, do którego nowego wierzchołka. „Słowo” to dowolny ciąg liter-kolorów. Następnie, jeśli na grafie podane jest kolorowanie, a x to jakiś wierzchołek, a w to jakieś słowo, to xw oznacza wierzchołek, do którego dotrzemy zaczynając od x i podążając za słowem w.

Kolorowanka nazywa się synchronizacja, jeśli istnieje słowo w prowadzące dowolny wierzchołek x do jednego ustalonego wierzchołka x 0 . W tym przypadku nazywa się w synchronizujące słowo. Pytanie zadawane przez problem kolorowania dróg brzmi: czy zawsze istnieje kolorowanie synchronizujące? Czy zawsze można pokolorować krawędzie grafu w taki sposób, aby wszystkie wierzchołki sprowadzić do jednego?

Problem ten ma zastosowania w kilku różnych obszarach, o czym można przeczytać na przykład w Wikipedii. Powiedzmy, w informatyce, w teorii automatów. Graf kolorujący można traktować jako deterministyczny automat skończony, w którym wierzchołki są stanami, a krawędzie wskazują, jak poruszać się między nimi. Załóżmy, że sterujemy tą maszyną na odległość, wysyłając polecenia jakimś kanałem informacyjnym i z powodu pewnych awarii kanał ten został zanieczyszczony, maszyna otrzymała jakieś błędne instrukcje i teraz nawet nie wiemy, w jakim jest stanie. Następnie, jeśli istnieje słowo synchronizacyjne, możemy doprowadzić je do znanego stanu, niezależnie od tego, gdzie się teraz znajduje.

Kiedy więc istnieje kolorowanie synchroniczne? Hipoteza o kolorowaniu dróg nakłada na graf jeszcze dwa ograniczenia (poza faktem, że każdy wierzchołek ma dokładnie d krawędzi). Po pierwsze, graf musi być silnie spójny – oznacza to, że istnieje droga z dowolnego wierzchołka do dowolnego innego. Po drugie, wykres nie może być okresowy. Wyobraźmy sobie, że wszystkie wierzchołki grafu można podzielić na zbiory V 1, V 2, ... V n, tak że dowolna krawędź grafu łączy wierzchołki z jakiegoś Vi i Vi+1 lub V n i V 0. Nie ma krawędzi pomiędzy wierzchołkami w każdym V i nie mogą one również „przeskakiwać” pomiędzy żadnymi V, tylko w odpowiedniej kolejności. Taki wykres nazywa się okresowym. Oczywiste jest, że taki graf nie może mieć kolorystyki synchronicznej, ponieważ niezależnie od tego, jak go pokolorujesz i bez względu na to, jakich słów użyjesz, dwa wierzchołki w różnych V i nigdy się nie spotkają - będą nadal chodzić w cyklu.

Twierdzenie o kolorowaniu dróg mówi, że następujące warunki są wystarczające: każdy nieokresowy, silnie połączony graf skierowany z d krawędziami z każdego wierzchołka ma kolorystykę synchroniczną. Po raz pierwszy została sformułowana jako hipoteza w 1970 r. i od tego czasu pojawiło się wiele częściowych wyników potwierdzających szczególne przypadki, ale pełny dowód pojawił się dopiero w 2007 r. Poniżej jest moje powtórzenie prawie całego dowodu (z wyjątkiem jednego lematu technicznego).

Okresowość

Na początek zastąpmy warunek nieokresowości innym równoważnym. Wykres jest okresowy wtedy i tylko wtedy, gdy istnieje liczba N>1, przez którą podzielona jest długość dowolnego cyklu na wykresie. Te. nasz wymóg nieokresowości jest równoznaczny z faktem, że takiego N nie ma, czyli innymi słowy, największy wspólny dzielnik długości wszystkich cykli na grafie wynosi 1. Udowodnimy, że każdy graf spełniający ten warunek ma synchronizacja kolorowania.

Udowodnienie, że okresowość jest równoważna warunkowi „istnieje N>1, przez który dzieli się długość dowolnego cyklu” jest trywialne z jednej strony i łatwe z drugiej. Jeśli chcesz to przyjąć na wiarę, możesz z łatwością pominąć resztę tego akapitu; dla pozostałej części dowodu nie ma to znaczenia. Jeśli wykres jest okresowy, tj. możemy podzielić wierzchołki na zbiory V 1, V 2, ... V n, tak aby krawędzie przechodziły między nimi wzdłuż cyklu, wtedy jest oczywiste, że długość dowolnego cyklu musi być podzielna przez n, tj. nowy warunek jest spełniony. To trywialny kierunek, ale do naszego zastąpienia potrzebujemy tylko drugiego kierunku. Załóżmy, że istnieje N>1, przez który dzieli się długość dowolnego cyklu. Zbudujmy na naszym grafie ukierunkowane drzewo rozpinające z korzeniem w wierzchołku r. Do dowolnego wierzchołka x w tym drzewie istnieje trasa rozpoczynająca się od pierwiastka o długości l(x). Twierdzimy teraz, że dla dowolnej krawędzi p-->q w grafie zachodzi zasada, że ​​l(q) = l(p) + 1 (mod N). Jeśli to stwierdzenie jest prawdziwe, to od razu wynika, że ​​możemy podzielić wszystkie wierzchołki na zbiory V i zgodnie z l(x) mod N, a graf będzie okresowy. Dlaczego to stwierdzenie jest prawdziwe? Jeśli p-->q jest częścią drzewa rozpinającego, to jest to oczywiste, ponieważ wtedy po prostu l(q) = l(p) + 1. Jeśli tak nie jest, to zapisujemy trasy od korzenia r do wierzchołki p,q jako R p i Rq. Niech także R r oznacza na wykresie drogę od q z powrotem do r (graf jest spójny, więc istnieje). Wtedy możemy napisać dwa cykle: R p p-->q R r , oraz R q R r . Zgodnie z warunkiem długości tych cykli dzielimy przez N, odejmując i redukując wartości całkowite, otrzymujemy, że l(p)+1 = l(q) mod N, co należało udowodnić.

Stabilna przyjaźń i indukcja

Niech będzie dane pewne zabarwienie grafu G. Nazwijmy dwa wierzchołki p,q przyjaciółmi, jeśli jakieś słowo w sprowadza ich do tego samego wierzchołka: pw = qw. Zadzwońmy p,q wrogów, jeśli „nigdy się nie spotkają”. Nazwijmy p,q stabilnymi przyjaciółmi, jeśli po wykonaniu dowolnego słowa w pozostaną przyjaciółmi: pw może nie dojść do tego samego wierzchołka co qw, ale po pewnym czasie w" może dojść. Stali przyjaciele nigdy nie staną się wrogami.

Relacja stabilności między wierzchołkami jest po pierwsze równoważnością (jest zwrotna, symetryczna i przechodnia), a po drugie zachowywana przez strukturę grafu: jeśli p, q są stabilnymi przyjaciółmi, p jest połączone krawędzią z p, q z q ", a te krawędzie tego samego koloru, to p" i q" są również stabilnymi przyjaciółmi. Oznacza to, że jest to stabilna przyjaźń stosowność i można podzielić przez: utwórz nowy graf G”, którego wierzchołki będą klasami równoważności dla trwałych przyjaźni w G. Jeśli w G jest przynajmniej jedna stabilna para, to G” będzie mniejsze od G. Ponadto, jeśli w pierwotnym grafie G z każdego wierzchołka miało d krawędzi, to w G" tak będzie. Na przykład, jeśli P jest wierzchołkiem nowego grafu, co jest klasą równoważności pierwotnych wierzchołków p1, p2... , a α jest dowolnym kolorem, wówczas krawędzie p1--α--> q1, p2---α-->q2, itd. prowadzą do wierzchołków q1, q2..., które są ze sobą trwale powiązane , a zatem leżą w jednym nowym wierzchołku Q, tak że wszystkie te krawędzie stają się nową krawędzią P --α-->Q. I tak dalej dla każdego z d kolorów.

Co więcej, jeśli G było nieokresowe, to G" również takie jest. W końcu - używając naszej alternatywnej definicji okresowości - każdy cykl w G zamienia się w cykl w G", więc jeśli wszystkie długości cykli w G" wynoszą podzielna przez n > 1, to to samo dotyczy wszystkich cykli w G. Zatem okresowość G” implikuje okresowość G.

Załóżmy, że udało nam się znaleźć kolorowanie synchroniczne w G. Można go teraz zastosować w G zamiast kolorowania, od którego zaczęliśmy: dowolna krawędź p-->q otrzyma nowy kolor zgodnie z nowym kolorem krawędzi P-->Q. Nieco dokładniej powinniśmy powiedzieć tak: w każdym wierzchołku P grafu G” nowe zabarwienie nadawane jest przez pewną permutację wszystkich kolorów π P: krawędź, która została pokolorowana kolorem α, otrzymuje nowy kolor π P (α) Następnie w oryginalnym grafie G dla każdego wierzchołka p z klasy stabilności P używamy tej samej permutacji π P do ponownego pokolorowania jego krawędzi. Nowe kolorowanie grafu G, ogólnie rzecz biorąc, definiuje pewne nowe pojęcia „przyjaźni”, „ wrogość” i „stabilność”, nie identyczne z pierwotnymi. Niemniej jednak, jeśli dwa wierzchołki p, q były stałymi przyjaciółmi w starym kolorowaniu - należały do ​​tej samej klasy P - to w nowym pozostaną stałymi przyjaciółmi. Dzieje się tak, ponieważ dowolny ciąg w, który przenosi p, q do jednego wierzchołka, można „przełożyć” ze starego kolorowania na nowe i odwrotnie, stosując permutację π P w każdym wierzchołku p wzdłuż drogi. Ponieważ p, q są stabilne w starym kolorowaniu i tak pozostanie „do końca”, każda pośrednia para wierzchołków p n , q n na drodze od p, q do wspólnego wierzchołka będzie stabilna, tj. będzie leżeć wewnątrz jednego wierzchołka P n i dlatego otrzyma tę samą permutację π P.

Nowe kolorowanie jest synchronizowane dla G”, tj. pewna sekwencja w sprowadza wszystkie wierzchołki do jednego wierzchołka P. Jeśli teraz zastosujemy w do nowego kolorowania w G, wówczas wszystkie wierzchołki zbiegną się gdzieś „wewnątrz P”. Jak stwierdzono powyżej, wszystkie wierzchołki klasy P pozostają stabilne w nowym kolorowaniu, co oznacza, że ​​możemy teraz kontynuować w, ponownie i ponownie łącząc pozostałe, wciąż oddzielne pary wierzchołków, aż wszystko zbiegnie się w jeden wierzchołek G. Tym samym nowe kolorowanie synchronizuje się dla G.

Z tego wszystkiego wynika, że ​​aby udowodnić twierdzenie, wystarczy udowodnić, że na każdym grafie spełniającym te warunki istnieje kolorowanie, w którym znajduje się para stabilnych przyjaciół. Bo wtedy z wykresu G można przejść do wykresu G" mniejszy rozmiar i również spełnia wszystkie warunki. Stosując argument indukcyjny, można założyć, że dla mniejszych grafów problem został już rozwiązany i wtedy kolorowanie synchroniczne dla G” będzie synchronizowane także dla G.

Kliki i zestawy maksymalne

Dla dowolnego podzbioru A wierzchołków grafu i słowa w, Aw oznacza zbiór wierzchołków, do którego dotrzemy zaczynając od wszystkich wierzchołków A i podążając za słowem w. Jeśli zaczniemy w ogóle od wszystkich wierzchołków grafu, to oznaczamy to przez Gw. W tym zapisie kolorowanie synchroniczne oznacza, że ​​istnieje w takie, że Gw jest zbiorem jednego elementu.

Jeśli zbiór wierzchołków A ma postać Gw dla pewnego w i dodatkowo dowolne dwa wierzchołki w A są wrogami, tj. nigdy się nie zbiegnie, nazwijmy A klika. Kliki istnieją, ponieważ zawsze możemy zacząć od całego G, wziąć parę zaprzyjaźnionych wierzchołków, przejść przez łączące je w i zmniejszyć liczbę wierzchołków o jeden; kontynuuj w ten sposób, aż pozostaną tylko wrogowie lub pozostanie tylko jeden wierzchołek - także w tym przypadku klika, po prostu banalna.

Jeśli A jest kliką, to dla dowolnego słowa w Aw jest także kliką; jest to jasne, ponieważ wrogowie pozostają wrogami. Jeśli x jest dowolnym wierzchołkiem grafu, to istnieje klika zawierająca x. Wynika to z faktu, że istnieje swego rodzaju klika A (patrz poprzedni akapit); jeśli p jest w nim wierzchołkiem, to istnieje słowo w prowadzące od p do x, ponieważ połączony wykres; wtedy Aw jest kliką zawierającą x.

Kliknięcia pomogą nam udowodnić, że istnieje pokolorowanie ze stabilnymi przyjaciółmi - zgodnie z poprzednią sekcją wystarczy to do udowodnienia twierdzenia. W tej sekcji udowodnimy, że jeśli istnieją dwie kliki A i B tak, że wszystkie znajdujące się w nich wierzchołki są wspólne z wyjątkiem jednego w A i jednego w B, to te dwa wierzchołki są stabilnymi przyjaciółmi. Zatem problem sprowadza się do znalezienia kolorowania zawierającego kliki A i B.

Aby lepiej zrozumieć działanie klik, warto przypisać wagi wierzchołkom grafu. Pokażmy, że możemy przypisać dodatnią wagę w(x) każdemu wierzchołkowi x, tak że jeśli dla dowolnego wierzchołka x zsumuj wagi wszystkich wierzchołków, z których wychodzą krawędzie w x, wówczas otrzymujemy d*w(x), gdzie d jest liczbą krawędzi z każdego wierzchołka. Wynika to z algebry liniowej i jeśli nie wiesz, czym jest wartość własna, pomiń resztę tego akapitu i przyjmij istnienie takiego w(x) za oczywistość. Jeśli M jest macierzą grafu G (komórka (i,j) wynosi 1, jeśli jest krawędź i->j, i 0, jeśli takiej krawędzi nie ma), to w(x), jak je opisałem, są elementami wektora własnego lewy ta macierz ma wartość własną d . Wiemy, że taki wektor istnieje, ponieważ d jest wartością własną: ma trywialny wektor własny po prawej(1,1,....1) - wynika to bezpośrednio z faktu, że z każdego wierzchołka wychodzi dokładnie d krawędzi.

Jeśli A jest dowolnym zbiorem wierzchołków, to w(A) oznacza sumę wag wszystkich wierzchołków z A; oraz w(G) jest sumą wag wszystkich wierzchołków grafu. Dodatkowo, jeśli s jest dowolnym słowem, to niech As -1 oznacza zbiór wierzchołków, do których dochodzimy z A, jeśli pójdziemy „w przeciwnym kierunku” wzdłuż s, przy każdym kroku zastępując każdy wierzchołek tymi wierzchołkami (jeśli istnieją) które trafiają do niej w odpowiednim kolorze.

Rozważmy teraz wszystkie zbiory wierzchołków, które można sprowadzić do jednego punktu, tj. takie A, że dla pewnego w Aw zawiera tylko jeden wierzchołek. Te zbiory A, które spośród wszystkich takich zbiorów mają maksymalną wagę w(A), będą nazywane zbiorami maksymalnymi. Jeśli kolorowanie jest synchronizowane, to cały graf G jest zbiorem maksymalnym (unikatowym), ale w przeciwnym razie tak nie jest.

Jeśli A jest dowolnym zbiorem wierzchołków, to suma wszystkich w(Aα -1), gdzie α przebiega po wszystkich d kolorach, jest równa d*w(A) - jest to po prostu uogólnienie głównej właściwości ciężaru z jeden wierzchołek do zbioru wierzchołków A. Jeżeli dodatkowo w tym przypadku A jest zbiorem maksymalnym, to każdy z w(Aα -1) nie może być większy od w(A), ponieważ te zbiory również są zredukowane do jednego wierzchołka . A ponieważ suma tych wag jest równa d*w(A), to okazuje się, że każda z nich jest równa w(A), a wszystkie te zbiory też są maksymalne. Wynika z tego natychmiast, że jeśli A jest maksymalne, to Aw -1 jest również maksymalne dla dowolnego słowa w.

Zbiory maksymalne są przydatne, ponieważ ich rozłączne wystąpienia mogą obejmować cały graf. Udowodnijmy to.

Miejmy zbiór zbiorów maksymalnych A 1 ...A n , rozłącznych parami i sprowadzonych do pojedynczych wierzchołków a 1 ...a n tym samym słowem w (w początkowym przypadku będzie n=1 i tylko jeden ustawiony, aby można było łatwo uruchomić). Jest oczywiste, że wszystkie a 1 ...an różnią się od siebie, ponieważ w przeciwnym razie możliwe byłoby dalsze rozszerzanie zbioru maksymalnego ze względu na elementy innego o tym samym wierzchołku końcowym. Załóżmy, że wszystkie Ai razem wzięte nie wyczerpały jeszcze wszystkich wierzchołków G i niech x będzie wierzchołkiem poza wszystkimi Ai. Ponieważ graf jest spójny, istnieje pewna droga h od a 1 do x. Następnie n zbiorów maksymalnych A i h -1 w -1 idzie zgodnie ze słowem whw do wierzchołków końcowych a 1 ...a n , a zbiór maksymalny A 1 trafia do jakiegoś wierzchołka Awhw = (Aw)hw = (a 1 h) w = xw. Ten wierzchołek xw także musi różnić się od wszystkich a 1 ...an , gdyż w przeciwnym razie maksymalny zbiór A i mógłby zostać uzupełniony o element x. A ponieważ wszystkie te zbiory n+1 – wszystkie A i h -1 w -1 plus A 1 – idą wzdłuż kierunku do różnych wierzchołków, wszystkie są rozłączne parami. Będziemy kontynuować tę ekspansję, aż poza zbiorem nie pozostaną żadne wierzchołki.

Możemy więc pokryć cały graf G rozłącznymi zbiorami maksymalnymi. Ponieważ są maksymalne, wszystkie mają tę samą całkowitą wartość wmax i dlatego ich liczba w pokryciu wynosi Nmax = w(G)/wmax.

Rozważmy teraz dowolny zbiór A składający się z wrogów w parach. Przykładem takiego zbioru jest np. klika (i także ma postać Gw). Zbiór maksymalny nie może zawierać pary wrogów, bo wtedy nie mógłby się zbiegać. Oznacza to, że w pokryciu N max zbiorów maksymalnych, każdy zawiera co najwyżej jeden element A, więc rozmiar A wynosi co najwyżej N max. W szczególności jest to górna granica wielkości dowolnej kliki.

Niech A będzie kliką postaci Gw, gdzie w jest jakimś słowem. Wtedy G = Aw -1 i odpowiednio w(G) jest równe sumie w(aw -1), gdzie a przebiega przez wszystkie wierzchołki A. Liczba wyrazów, zgodnie z poprzednim akapitem, wynosi nie więcej niż N max, a każdy zbiór aw -1 można sprowadzić do jednego punktu (w punkcie a ze słowem w), tak aby jego waga nie była większa niż maksymalna w max . Ponieważ cała suma jest równa w(G) = Nmax *wmax, dochodzimy do wniosku, że liczba wyrazów jest dokładnie równa Nmax, a każdy wyraz jest dokładnie równy wmax. Udowodniliśmy, że wszystkie kliki mają ten sam rozmiar: dokładnie N max elementów.

Niech będą dwie kliki A i B takie, że wewnątrz A wszystkie elementy są wspólne z B z wyjątkiem jednego: |A| - |A∩B| = 1.

Ponieważ A i B są tej samej wielkości, mamy również |B| - |A∩B| = 1, tj. A i B mają wszystkie elementy wspólne, z wyjątkiem jednego wierzchołka p w A i jednego wierzchołka q w B. Chcielibyśmy udowodnić, że te wierzchołki p,q są stabilnymi przyjaciółmi. Jeśli tak nie jest, to jakieś słowo w czyni ich wrogami, tj. pw i qw są wrogami. Jak pokazano powyżej, Aw i Bw są także klikami i oczywiste jest, że wszystkie ich elementy są wspólne, z wyjątkiem wrogów pw i qw. Wtedy zbiór Aw ∪ Bw jest zbiorem wrogów parami. Rzeczywiście, wszystkie elementy Aw są w nim wrogami parami, ponieważ jest to klika; to samo dotyczy elementów Bw; i pozostała tylko para pw,qw - także wrogowie. Ale ten zestaw ma N maks. +1 elementów, a powyżej pokazaliśmy, że żaden zestaw wrogów w parach nie może mieć więcej niż N maks. elementów. Jest to sprzeczność i dlatego pw i qw nie mogą być wrogami żadnego w. Innymi słowy, p i q są stabilnymi przyjaciółmi.

Rozciągające się wykresy i kliki

Weźmy wszystkie wierzchołki danego grafu G i wybierzmy tylko jedną krawędź wychodzącą z każdego wierzchołka. Wybór ten wyznacza podgraf, który nazywamy wykres obejmujący(wykres obejmujący). Może istnieć wiele różnych wykresów obejmujących, ale zastanówmy się trochę nad tym, jak one wyglądają. Niech istnieje pewien graf rozpinający R. Jeśli weźmiemy w nim dowolny wierzchołek x i zaczniemy podążać za jego krawędziami, to za każdym razem będziemy mieli jeden wybór, bo w R z każdego wierzchołka wychodzi tylko jedna krawędź i prędzej czy później później zamkniemy cykl. Być może ten cykl nie zakończy się w x, ale zamknie się gdzieś „dalej” – na przykład x-->y-->z-->s-->y. Wtedy „ogon” tego cyklu będzie prowadził od x. Jeśli zaczniemy od jakiegoś innego wierzchołka, to na pewno też skończymy na cyklu – tym czy innym. Okazuje się, że dowolny wierzchołek R albo leży na cyklu (których może być kilka), albo jest częścią „ogona” prowadzącego do cyklu. Oznacza to, że R wygląda tak: pewna liczba cykli i zbudowana na nich pewna liczba „odwróconych” drzew: każde drzewo nie zaczyna się, ale kończy na „korzeńu”, który leży na jednym z cykli.

Możemy przypisać do każdego wierzchołka grafu poziom, odpowiadająca jego odległości do cyklu na danym grafie rozpinającym R. Wierzchołki leżące na cyklu mają poziom 0, a wierzchołki leżące na drzewie dołączonym do cyklu otrzymują poziom równy odległości w ich drzewie od „pierwiastka” ” leżąc na rowerze. Niektóre wierzchołki naszego grafu mają maksymalny poziom L. Być może jest on nawet równy 0 – tj. nie ma drzew, są tylko cykle. Być może jest on większy od zera, a wierzchołki tego maksymalnego poziomu leżą na najróżniejszych drzewach, połączonych z różnymi cyklami lub z jednym.

Chcemy wybrać graf rozpinający R taki, że wszystkie wierzchołki maksymalnego poziomu leżą na tym samym drzewie. Intuicyjnie można by sądzić, że da się to zrobić, bo jeśli tak nie jest – np. są porozrzucane różne drzewa- wtedy możesz wybrać jeden z tych maksymalnych wierzchołków x i zwiększyć jego poziom dołączając do R jakąś krawędź prowadzącą do x. Wtedy trzeba będzie wyrzucić jakieś inne żebro i nie jest faktem, że nie zaszkodzi to czemuś innemu... ale to kwestia techniczna, o której będziemy rozmawiać później. Próbuję tylko powiedzieć, że intuicyjnie nie wydaje się to bardzo skomplikowane.

Na razie załóżmy, że możemy wybrać R tak, aby wszystkie wierzchołki maksymalnego poziomu leżały na tym samym drzewie. Zakłada się, że drzewo to jest nietrywialne, tj. maksymalny poziom L > 0. Na podstawie tego założenia skonstruujemy kolorowanie, w którym znajdują się kliki A i B spełniające warunki z poprzedniego podrozdziału, co dowodzi, że w tym kolorowaniu istnieje stabilna para przyjaciele.

Kolorowanie będzie wyglądało następująco: wybierz jakiś kolor α i pomaluj tym kolorem wszystkie krawędzie grafu R, a wszystkie pozostałe krawędzie grafu G innymi kolorami w dowolny sposób (jeśli jest tylko jeden kolor, to R pokrywa się z G , więc nie ma problemu). Zatem słowa składające się z koloru α „popychają” wierzchołki R wzdłuż swoich drzew w kierunku cykli, a następnie prowadzą je przez cykle. To jedyne słowa, które będą nam potrzebne.

Niech x będzie dowolnym wierzchołkiem maksymalnego poziomu L w R i niech K będzie dowolną kliką zawierającą x; wiemy, że taka klika istnieje. Czy K może zawierać jakiś inny wierzchołek maksymalnego poziomu L? Zgodnie z naszym założeniem wszystkie takie wierzchołki znajdują się w tym samym drzewie co x, co oznacza, że ​​słowo α L przenosi je w to samo miejsce co x, czyli do korzenia tego drzewa, który leży na cyklu. Oznacza to, że wszystkie takie wierzchołki są przyjaciółmi x i dlatego nie mogą należeć do tej samej kliki co on. Dlatego oprócz x, K może zawierać tylko wierzchołki niższego poziomu.

Przyjrzyjmy się zbiorowi A = Kα L-1. To także jest klika i w niej wszystkie wierzchołki, z wyjątkiem x, osiągnęły pewien rodzaj cyklu w R, ponieważ wszystkie wierzchołki A, z wyjątkiem x, mają poziom niższy niż L. Tylko x pozostaje poza cyklem, w punkcie odległość dokładnie 1 do pierwiastka w cyklu. Weźmy teraz pewną liczbę m, która jest wielokrotnością wszystkich długości cykli w R – na przykład iloczynem wszystkich długości cykli. m ma tę cechę, że jeśli wierzchołek y należy do cyklu w R, to słowo α m przywraca go na swoje miejsce: yα m = y. Spójrzmy na klikę B = Aα m . Wszystkie wierzchołki A, z wyjątkiem x, leżały na cyklach i dlatego pozostały w B; i tylko x w końcu wszedł w swój cykl i gdzieś tam się osiedlił. Oznacza to, że przecięcie A i B zawiera wszystkie wierzchołki A z wyjątkiem jednego: |A| - |A∩B| = 1. Ale to oznacza, zgodnie z poprzednią sekcją, że nasze kolorowanie ma stabilną parę, co musieliśmy udowodnić.

Budowanie maksymalnego poziomu.

Pozostaje udowodnić, że zawsze można wybrać taki graf rozpinający R, aby miał on nietrywialny poziom maksymalny L > 0, a wszystkie wierzchołki tego poziomu leżały na tym samym drzewie.

Częścią tego dowodu jest dość nudny i techniczny lemat, który przeczytałem i sprawdziłem, ale nie będę go powtarzał, powiem tylko, gdzie to jest w artykule dla zainteresowanych. Ale powiem ci, jak dojść do tego lematu.

Będziemy potrzebować dwóch ograniczeń, które możemy nałożyć na graf G. Najpierw załóżmy, że G nie ma pętli, tj. krawędzie od wierzchołka do tego samego wierzchołka. Rzecz w tym, że jeśli na wykresie jest pętla, to bardzo łatwo w inny sposób znaleźć kolorowanie synchroniczne. Pokolorujmy tę pętlę kolorem α, a następnie idąc od tego wierzchołka w przeciwnym kierunku „w stronę strzałek” pokolorujmy krawędzie tak, aby kolor α zawsze prowadził do tego wierzchołka. Ponieważ graf jest spójny, łatwo to ułożyć, a wtedy pętla zapewnia, że ​​w pewnym stopniu α sprowadzi cały wykres do tego wierzchołka.

Następnie załóżmy na sekundę, że z jakiegoś wierzchołka p wszystkie d krawędzie prowadzą do tego samego wierzchołka q. Pozwalają na to warunki, ale w tym przypadku nazwiemy ten zbiór krawędziami garść. Nasze drugie ograniczenie jest następujące: nie ma wierzchołka r, do którego prowadzą dwa łącza z różnych wierzchołków p i q. Dlaczego możemy to narzucić? Ponieważ jeśli z p i q są połączenia w r, to dla dowolnego kolorowanie p, q zbiegną się w wierzchołku r po pierwszym kolorze i dlatego są stabilnymi przyjaciółmi. Zatem w tym przypadku nie potrzebujemy całej konstrukcji rozpinających grafów i klik, od razu zyskujemy stabilnych przyjaciół. Dlatego możemy założyć, że tak nie jest.

Na koniec udowadniamy, że zawsze istnieje graf rozpinający R, w którym nie wszystkie wierzchołki leżą na cyklach, ale istnieją pewne nietrywialne drzewa. Wybierzmy jakiś R i załóżmy, że wszystkie jego wierzchołki leżą na cyklach. Gdyby wszystkie krawędzie grafu G były połączone, tj. zawsze wszystkie d krawędzie wychodzące z tego samego wierzchołka prowadziły do ​​tego samego wierzchołka - wtedy wybór R polegałby na wybraniu tylko jednej krawędzi z każdego połączenia. W tym przypadku cykl w R mógłby być tylko jeden (w końcu kilka cykli w R nie mogłoby być ze sobą połączonych w spójnym grafie G - wszystkie krawędzie G łączą tylko te same wierzchołki, co krawędzie R, bo to są łączniki - a ponieważ G jest spójny, to jest niemożliwe), a każdy cykl w G po prostu wybiera inne krawędzie z połączeń tego cyklu, ale w istocie jest to ten sam cykl, o tej samej długości. Oznacza to jednak, że długości wszystkich cykli w G są podzielne przez tę długość, co dokładnie zaprzecza nieokresowości G. Nie może więc być tak, że wszystkie krawędzie w G leżą na ogniwach, co oznacza, że ​​istnieją jakieś dwie krawędzie p-->q w R i p-->s poza R (potrzebowaliśmy długiego argumentu na temat spójników, aby udowodnić, że jakaś krawędź z p nie tylko nie leży w grafie rozpinającym, ale także prowadzi do innego wierzchołka s). Następnie zastępujemy p-->q p-->s, co „przerwie” cykl, tworząc w nim swego rodzaju nietrywialny ogon. Ten ogon da nam nietrywialne drzewo na nowym wykresie.

Teraz możemy wybrać spośród wszystkich grafów rozpinających R zawierających nietrywialne drzewa jakiś R, który ma maksymalną liczbę wierzchołków w cyklach. To jest ma wierzchołki, które nie należą do cykli, ale poza tym ograniczeniem liczba wierzchołków w cyklach jest zmaksymalizowana. Na tym wykresie jest kilka wierzchołków maksymalnego poziomu L i możemy założyć, że znajdują się one na drzewach prowadzących do różnych korzeni, w przeciwnym razie osiągnęliśmy już to, czego potrzebowaliśmy. Wybierzmy jeden taki wierzchołek x. Chcemy zmienić graf tak, aby ten wierzchołek stał się częścią dłuższej trasy w drzewie, dłuższej niż L, a pozostałe drzewa się nie zmieniły, a wtedy maksymalny poziom będzie tylko w jednym drzewie, a tego właśnie chcemy. Wykres możesz zmienić na trzy sposoby:

a) weź krawędź y-->x i dodaj ją do R i odrzuć istniejącą krawędź y-->z;
b) weź krawędź b-->r, która jest ostatnią na ścieżce od x do swojego cyklu (r w cyklu), wyrzuć ją i dodaj inną b-->z.
c) weź krawędź c-->r, która jest częścią cyklu, odrzuć ją i dodaj inną c-->z.

Lemat 7 pracy Trakhtmana szczegółowo dowodzi, że jedna (a w niektórych przypadkach dwie) z tych zmian prowadzi do pożądanego rezultatu. W procesie wykorzystuje się zarówno maksymalizację R (jeżeli jakaś zmiana prowadzi do powstania grafu o większej liczbie wierzchołków na cyklach niż w R, jest to sprzeczne z jego maksymalnością), jak i zdefiniowany powyżej warunek, że nie ma wierzchołka, do którego prowadzą dwa ogniwa. W rezultacie w każdym przypadku otrzymujemy graf R, w którym wszystkie wierzchołki maksymalnego poziomu leżą na jednym nietrywialnym drzewie.

Aktualizacja, tydzień później: Niemniej jednak zdecydowałem się uczynić ten wpis całkowicie samowystarczalnym i także powtórzyć dowód lematu, do którego odwoływałem się w poprzednim akapicie. Lepiej byłoby to zrobić za pomocą diagramu, ale nie chce mi się tego rysować ani wyrywać z artykułu, więc spróbuję słowami. Wyobraźmy sobie więc, że mamy graf rozpinający R, w którym znajdują się nietrywialne drzewa, i wszystkich takich grafów w nim maksymalna ilość wierzchołki leżą na cyklach. Naszym celem jest przekształcenie R w graf rozpinający, w którym wszystkie wierzchołki maksymalnego poziomu leżą na tym samym drzewie; Gdy tylko w trakcie próby otrzymamy taki graf, od razu kończymy (i nie obchodzi nas, że może zostać utracona maksymalizacja wykresu pod względem liczby wierzchołków na cyklach, nie jest to dla nas ważne w sam, używamy go tylko w procesie). Niech x będzie wierzchołkiem maksymalnego poziomu L, T drzewem, na którym się on znajduje, r wierzchołkiem cyklu C, w którym kończy się T, b-->r ostatnią krawędzią przed r na ścieżce od x do cyklu C. Można założyć, że do tego cyklu dołączają jeszcze jakieś inne drzewa lub takie, które mają wierzchołki poziomu L - w przeciwnym razie wszystko już zostało zrobione. Wynika z tego, że jeśli uda nam się uzyskać z T drzewo z elementem większym niż L i nie przedłużać pozostałych drzew, to skończymy.

Najpierw spróbujmy wykonać operację a) powyżej: weźmy krawędź y-->x w G - istnieje, ponieważ Wykres jest spójny i pozbawiony pętli i nie leży w R, ponieważ x maksymalny poziom. Dodajmy to do R i wyrzućmy trochę y-->z, które było tam wcześniej. Jeśli y leży na drzewie T, to y-->x zamyka nowy cykl, a w nowym grafie więcej wierzchołków leży na cyklach, a nadal istnieją nietrywialne drzewa (przynajmniej te inne, które były w R), co zaprzecza maksymalizacji R. Jeśli y nie leży na T i y-->z nie jest częścią cyklu C, to usunięcie y-->z nie przerywa tego cyklu, ale dodanie y-->x wydłuża maksimum poziom drzewa T przynajmniej o jeden, a w innych drzewa się nie wydłużają, więc gotowe. Pozostała opcja ma miejsce, gdy y-->z leży na cyklu C, który właśnie się przerwał, i utworzył się nowy cykl: od r do y, następnie y-->x, następnie od x do r wzdłuż dawne drzewo. Długość tego cyklu wynosi l(ry)+1+L, a długość starego cyklu C wynosiła l(ry)+1+l(zr). Nowy cykl nie może być dłuższy od starego, zaprzecza to maksymalności R, więc widzimy, że L ≤ l(zr), tj. długość trasy od z do r w starej pętli. Z drugiej strony na nowym grafie wierzchołek z ma teraz poziom co najmniej l(zr), a jeśli jest on większy niż L, to koniec. Możemy więc założyć, że l(zr)=L. Reasumując: zakładamy, że a) nie działa i wiemy, że y-->z leży w cyklu C, l(zr) = L.

Teraz spróbujmy wykonać operację b): zamień krawędź b-->r na inną krawędź b-->d. Zobaczmy, gdzie leży nowy wierzchołek d. Jeśli na drzewie T, to stworzyliśmy nowy cykl nie przerywając poprzedniego i obaliliśmy maksymalność R. Jeśli na innym drzewie, to maksymalne wierzchołki T, łącznie z x, będą miały teraz poziom większy niż L, oraz inne drzewa nie będą i to koniec. Jeśli w innym cyklu, a nie w C, to teraz zrobimy razem z b) także a): ponieważ wiemy, że y-->z leży na C, to ta operacja podzieli C, ale nie nowy cykl, na który to jest teraz połączonym drzewem T i na tym drzewie będą teraz wierzchołki o poziomie większym niż L i znowu skończymy.

Pozostała opcja ma miejsce, gdy b-->d jest również połączone z obiegiem C, w innym miejscu niż r, lub w tym samym miejscu i wtedy d=r. Po zamianie b-->r na b-->d otrzymaliśmy tę samą sytuację co na początku - drzewo T, wierzchołek x poziomu L itd. - tylko drzewo jest teraz połączone z cyklem przez wierzchołek d. Rozważając teraz operację a), wnioskujemy (zakładając, że to nie działa), że l(zd) = L, tak jak poprzednio doszliśmy do wniosku, że l(zr) = L. Ale jeśli l(zd) = l( zr), tj. odległość w cyklu od z jest taka sama do d i r, to jest to ten sam wierzchołek: d=r. Jeśli więc b) nie działa, to każda krawędź z b musi prowadzić do r, tj. krawędzie z b tworzą połączenie.

Na koniec rozważmy krawędź c -> r leżącą na cyklu C. Ponieważ możemy założyć, że wszystkie krawędzie z b leżą na łączu prowadzącym do r, możemy również nałożyć wspomniane powyżej ograniczenie, że nie może być dwóch ogniw prowadzących do jeden wierzchołek, nie wszystkie krawędzie od c prowadzą do r, ale jest pewna krawędź c-->e. Zamieńmy c-->r na c-->e. Gdzie może leżeć wierzchołek e? Nie na drzewie T, bo to „wydłużyłoby” cykl C, zaprzeczając maksymalności R. Zatem e leży na innym drzewie lub na innym cyklu, a nawet na tym samym cyklu C, ale nie w wierzchołku r. Następnie drzewo T, zanim dołączy do pętli, zostanie teraz przedłużone przynajmniej o jedną krawędź wychodzącą z r, a może o więcej (tylko o jedną, jeśli e leży bezpośrednio po r i c-->e ponownie zamyka pętlę C, wyprowadzając z tego tylko r). Oznacza to, że wierzchołek x i inne maksymalne wierzchołki T mają teraz poziom nie mniejszy niż L+1, a pozostałe drzewa nie uległy wydłużeniu i znów mamy to, czego potrzebujemy.