Uzasadnij, że dla każdego grafu zachodzi nierówność

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
lola456
Użytkownik
Użytkownik
Posty: 38
Rejestracja: 16 lis 2019, o 21:50
Płeć: Kobieta
wiek: 19
Podziękował: 13 razy

Uzasadnij, że dla każdego grafu zachodzi nierówność

Post autor: lola456 » 11 sty 2020, o 18:01

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?
Rekrutacja Instytut Matematyczny, Uniwersytet Wrocławski (gif)

Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 8747
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 37 razy
Pomógł: 1855 razy

Re: Uzasadnij, że dla każdego grafu zachodzi nierówność

Post autor: Dasio11 » 11 sty 2020, o 23:31

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}\).

lola456
Użytkownik
Użytkownik
Posty: 38
Rejestracja: 16 lis 2019, o 21:50
Płeć: Kobieta
wiek: 19
Podziękował: 13 razy

Re: Uzasadnij, że dla każdego grafu zachodzi nierówność

Post autor: lola456 » 12 sty 2020, o 11:04

Dasio11 pisze:
11 sty 2020, o 23:31
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}\).
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.

Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 8747
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 37 razy
Pomógł: 1855 razy

Re: Uzasadnij, że dla każdego grafu zachodzi nierówność

Post autor: Dasio11 » 12 sty 2020, o 12:36

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}\).

lola456
Użytkownik
Użytkownik
Posty: 38
Rejestracja: 16 lis 2019, o 21:50
Płeć: Kobieta
wiek: 19
Podziękował: 13 razy

Re: Uzasadnij, że dla każdego grafu zachodzi nierówność

Post autor: lola456 » 13 sty 2020, o 09:19

Dasio11 pisze:
12 sty 2020, o 12:36
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}\).
Rzeczywiście twierdzenie jest wtedy błędne.
A co jeśli mamy iloczyn liczby chromatycznej grafu i liczby chromatycznej dopełnienia tego grafu?

ODPOWIEDZ