Czy graf k-krytyczne moze byc nieskonczony?

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
kingataranek
Użytkownik
Użytkownik
Posty: 38
Rejestracja: 28 paź 2007, o 12:53
Płeć: Kobieta
Lokalizacja: czestochowa
Podziękował: 5 razy

Czy graf k-krytyczne moze byc nieskonczony?

Post autor: kingataranek »

A dokladnie:
Czy graf k-krytyczny moze miec policzlnie nieskonczona liczbe wierzcholkow.
Ja mysle, ze nie moze, ale nie mam pojecia jak to udowodnic.
Prosze o pomoc
Dzieki
xiikzodz
Użytkownik
Użytkownik
Posty: 1874
Rejestracja: 4 paź 2008, o 02:13
Płeć: Kobieta
Lokalizacja: Lost Hope
Podziękował: 28 razy
Pomógł: 502 razy

Czy graf k-krytyczne moze byc nieskonczony?

Post autor: xiikzodz »



masz tam fakt (Theorem 1.), z ktorego wynika, ze kazdy graf krytyczny jest skonczony.
kingataranek
Użytkownik
Użytkownik
Posty: 38
Rejestracja: 28 paź 2007, o 12:53
Płeć: Kobieta
Lokalizacja: czestochowa
Podziękował: 5 razy

Czy graf k-krytyczne moze byc nieskonczony?

Post autor: kingataranek »

Sorry, ale nie bardzo to jest dla mnie jasne, bo ta teoria mowi o tym ze G nie moze byc (k+1) - colourable, ale przeciez numer chromatyczny moze byc mniejszy od k.
Tzn subgraph moze byc k- colourable ale miec numer chromatyczny 2, a G moze miec numer chromatyczny 3 i wtedy jest krytyczny?
xiikzodz
Użytkownik
Użytkownik
Posty: 1874
Rejestracja: 4 paź 2008, o 02:13
Płeć: Kobieta
Lokalizacja: Lost Hope
Podziękował: 28 razy
Pomógł: 502 razy

Czy graf k-krytyczne moze byc nieskonczony?

Post autor: xiikzodz »

W twierdzeniu jest wszystko, jak nalezy i trudno o jasniejsze sformulowanie. Jesli bariere stanowi jezyk, to sluze tlumaczeniem:

Twierdzenie 1. Niech \(\displaystyle{ k}\) bedzie liczba naturalna dodatnia i niech graf \(\displaystyle{ G}\) ma te wlasnosc, ze kazdy jego skonczony podgraf jest \(\displaystyle{ k}\)-kolorowalny. Wowczas graf \(\displaystyle{ G}\) jest \(\displaystyle{ k}\)-kolorowalny.

Teza twojego zadania wynika z tego twierdzenia natychmiast. Jesli bowiem graf nieskonczony bylby \(\displaystyle{ k}\)-krytyczny, to kazdy jego podgraf, w tym kazdy jego podgraf skonczony bylby \(\displaystyle{ k-1}\)-kolorowalny i wobec twierdzenia graf \(\displaystyle{ G}\) rowniez, co przeczy jego \(\displaystyle{ k}\)-krytycznosci.
kingataranek
Użytkownik
Użytkownik
Posty: 38
Rejestracja: 28 paź 2007, o 12:53
Płeć: Kobieta
Lokalizacja: czestochowa
Podziękował: 5 razy

Czy graf k-krytyczne moze byc nieskonczony?

Post autor: kingataranek »

Dziekuje bardzo
ODPOWIEDZ