Uzasadnij, że dla każdego grafu G zachodzi nierówność \(\displaystyle{ X(G) * \vec{X(G)} \ge \left| G \right| }\)
Przepraszam za zapis ale nie wiedziałam, jak zapisać indeks chromatyczny.
Czy ktoś mógłby mi pomóc rozwiązać to zadanie?
Uzasadnij, że dla każdego grafu zachodzi nierówność
- Dasio11
- Moderator
- Posty: 10218
- Rejestracja: 21 kwie 2009, o 19:04
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 40 razy
- Pomógł: 2361 razy
Re: Uzasadnij, że dla każdego grafu zachodzi nierówność
Jeśli po lewej stronie stoi iloczyn liczby chromatycznej i indeksu chromatycznego \(\displaystyle{ G}\), to nierówność jest nieprawdziwa, o czym świadczy każdy cykl długości \(\displaystyle{ \ge 5}\).
-
- Użytkownik
- Posty: 71
- Rejestracja: 16 lis 2019, o 21:50
- Płeć: Kobieta
- wiek: 19
- Podziękował: 36 razy
- Pomógł: 1 raz
Re: Uzasadnij, że dla każdego grafu zachodzi nierówność
Nierówność wtedy jest prawdziwa, ponieważ mamy \(\displaystyle{ 3 \cdot 3 \ge 5 }\).
Ostatnio zmieniony 12 sty 2020, o 11:16 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Symbol mnożenia to \cdot.
Powód: Symbol mnożenia to \cdot.
- Dasio11
- Moderator
- Posty: 10218
- Rejestracja: 21 kwie 2009, o 19:04
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 40 razy
- Pomógł: 2361 razy
Re: Uzasadnij, że dla każdego grafu zachodzi nierówność
Faktycznie, poprawiam: tezie przeczy dowolny cykl długości przynajmniej \(\displaystyle{ 10}\), a także dowolny cykl długości parzystej i nie mniejszej od \(\displaystyle{ 5}\).
-
- Użytkownik
- Posty: 71
- Rejestracja: 16 lis 2019, o 21:50
- Płeć: Kobieta
- wiek: 19
- Podziękował: 36 razy
- Pomógł: 1 raz
Re: Uzasadnij, że dla każdego grafu zachodzi nierówność
Rzeczywiście twierdzenie jest wtedy błędne.
A co jeśli mamy iloczyn liczby chromatycznej grafu i liczby chromatycznej dopełnienia tego grafu?