Udowodnić, że w \(\displaystyle{ K_6}\) dowolnie pokolorowanym krawędziowo na 2 kolory jest trójkąt monochromatyczny, ale w \(\displaystyle{ K_5}\) już nie.
Jak mozna to rozwiązać ?
kolorwanie 2oma kolorami krawędzi
- yorgin
- Użytkownik
- Posty: 12762
- Rejestracja: 14 paź 2006, o 12:09
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 17 razy
- Pomógł: 3440 razy
kolorwanie 2oma kolorami krawędzi
Przypadek \(\displaystyle{ K_6}\).
Ustal jeden wierzchołek grafu. Z zasady szufladkowej Dirichleta wynika, że istnieją trzy krawędzie jednego koloru (powiedzmy czerwone) wychodzące z tego wierzchołka. Spróbuj teraz kolorować krawędzie łączące wierzchołki, które połączyłeś czerwonymi krawędziami ze startowym wierzchołkiem.
Przypadek \(\displaystyle{ K_5}\).
Istnieje kolorowanie zawierające trójkąt monochromatyczny. Zapewne chodzi więc o wskazanie kolorowania bez takiego trójkąta. No to jest wyłącznie metoda prób i błędów.
Ustal jeden wierzchołek grafu. Z zasady szufladkowej Dirichleta wynika, że istnieją trzy krawędzie jednego koloru (powiedzmy czerwone) wychodzące z tego wierzchołka. Spróbuj teraz kolorować krawędzie łączące wierzchołki, które połączyłeś czerwonymi krawędziami ze startowym wierzchołkiem.
Przypadek \(\displaystyle{ K_5}\).
Istnieje kolorowanie zawierające trójkąt monochromatyczny. Zapewne chodzi więc o wskazanie kolorowania bez takiego trójkąta. No to jest wyłącznie metoda prób i błędów.
-
- Użytkownik
- Posty: 1922
- Rejestracja: 26 mar 2012, o 18:52
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 695 razy
- Pomógł: 4 razy
kolorwanie 2oma kolorami krawędzi
Ok, no faktycznie widzę, że "musi" wyjść jeden trójkąt, ale nie wiem jak powinienem to sformalizować. Napiszę najlepiej jak potrafię, sam ocenisz.
No widać, że żółta linia na koniec symbolizuje, że to koniec - ona musi być czerwona, niebieska - tak czy inaczej zamknie trójkąt. A 2gi etap został wykonany w sposób "przymuszony" Gdyby te linie były inne, to wówczas zamykamy od razy trójkąt chromatyczny.
Jednak to jeszcze nie jest dowód przecież. 1szy etap (wybór 3 krawędzi nie jest Ok)
Chodzi o to, że 3 krawędzie będą na prawdę tego samego koloru (co najmniej 3), ale ja byłem trochę tendecyjny przy wyborze.
Co powiesz o tym 1szym etapie ? On nie był zupełnie dowolny - tzn wybrałem 3 do kolorwania na jeden kolor - ale wybrałem 3 szczególne w jakiś sposób.
No widać, że żółta linia na koniec symbolizuje, że to koniec - ona musi być czerwona, niebieska - tak czy inaczej zamknie trójkąt. A 2gi etap został wykonany w sposób "przymuszony" Gdyby te linie były inne, to wówczas zamykamy od razy trójkąt chromatyczny.
Jednak to jeszcze nie jest dowód przecież. 1szy etap (wybór 3 krawędzi nie jest Ok)
Chodzi o to, że 3 krawędzie będą na prawdę tego samego koloru (co najmniej 3), ale ja byłem trochę tendecyjny przy wyborze.
Co powiesz o tym 1szym etapie ? On nie był zupełnie dowolny - tzn wybrałem 3 do kolorwania na jeden kolor - ale wybrałem 3 szczególne w jakiś sposób.
- yorgin
- Użytkownik
- Posty: 12762
- Rejestracja: 14 paź 2006, o 12:09
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 17 razy
- Pomógł: 3440 razy
kolorwanie 2oma kolorami krawędzi
I o to właśnie chodziło w tej części. Przez rozpatrzenie przypadków można łatwo dojść do jednokolorowego trójkąta.matinf pisze: No widać, że żółta linia na koniec symbolizuje, że to koniec - ona musi być czerwona, niebieska - tak czy inaczej zamknie trójkąt. A 2gi etap został wykonany w sposób "przymuszony" Gdyby te linie były inne, to wówczas zamykamy od razy trójkąt chromatyczny.
No to wybierz jakiekolwiek trzy inne i powtórz rozumowanie i rysunki z tego szczególnego, opisanego wyżej. Dostaniesz analogiczne obrazki i wyciągniesz analogiczne wnioski.matinf pisze: Jednak to jeszcze nie jest dowód przecież. 1szy etap (wybór 3 krawędzi nie jest Ok)
Chodzi o to, że 3 krawędzie będą na prawdę tego samego koloru (co najmniej 3), ale ja byłem trochę tendecyjny przy wyborze.
Co powiesz o tym 1szym etapie ? On nie był zupełnie dowolny - tzn wybrałem 3 do kolorwania na jeden kolor - ale wybrałem 3 szczególne w jakiś sposób.
Jeżeli chcesz to zrobić formalnie, to możesz ustalić wierzchołek \(\displaystyle{ v}\) i dobrać wierzchołki \(\displaystyle{ a, b, c}\) a następnie wziąć czerwone krawędzie niezorientowane \(\displaystyle{ (v,a), (v,b), (v,c)}\). Z zasady szufladkowej wiemy, że mamy takie trzy krawędzie, które mają etykiety czerwone i je właśnie wybraliśmy. Aby nie dostać trójkąta jednokolorowego, jaką etykietę przypiszesz krawędziom \(\displaystyle{ (a,b)}\) oraz \(\displaystyle{ (c,b)}\)? Co wtedy z krawędzią \(\displaystyle{ (a,c)}\)? Czy zmiana wyboru pary krawędzi wpływa na dalsze rozwiązanie?
-
- Użytkownik
- Posty: 5101
- Rejestracja: 11 mar 2011, o 16:31
- Płeć: Mężczyzna
- Lokalizacja: 52°16'37''N 20°52'45''E
- Podziękował: 4 razy
- Pomógł: 1001 razy
kolorwanie 2oma kolorami krawędzi
Oprócz metody prób i błędów są jeszcze co najmniej dwie:yorgin pisze:No to jest wyłącznie metoda prób i błędów.
1. Przyjrzeć się dowodowi dla sześciu wierzchołków. Wywnioskować, że w kontrprzykładzie dla pięciu z każdego wierzchołka muszą wychodzić po dwie krawędzie każdego koloru.
2. Przypadkiem natknąć się na rysunek pięciokąta, w którym boki są jednego koloru, a przekątne innego.