Mam takie twierdzenie:
Niech G będzie grafem n-wierzchołkowym. Wtedy
\(\displaystyle{ i(G) \leq n- \Delta}\).
Nie wiem jak zrobić do tego dowód. Może ktoś wie jak go zrobić albo chociaż gdzie mogę go znaleźć?
Bardzo proszę o pomoc.
dolna liczba niezależności i(G)-oszacowanie
-
- Użytkownik
- Posty: 11
- Rejestracja: 10 maja 2012, o 10:54
- Płeć: Kobieta
- Lokalizacja: Rzeszów
- Podziękował: 1 raz
-
- Użytkownik
- Posty: 11
- Rejestracja: 10 maja 2012, o 10:54
- Płeć: Kobieta
- Lokalizacja: Rzeszów
- Podziękował: 1 raz
dolna liczba niezależności i(G)-oszacowanie
\(\displaystyle{ i(G)}\) - dolna liczba niezależności w grafie
\(\displaystyle{ \Delta}\) - maksymalny stopień wierzchołka grafu
\(\displaystyle{ \Delta}\) - maksymalny stopień wierzchołka grafu