Liczba niezależności w grafie
-
- Użytkownik
- Posty: 9
- Rejestracja: 29 cze 2020, o 18:53
- Płeć: Mężczyzna
- wiek: 21
- Podziękował: 2 razy
Liczba niezależności w grafie
Czy istnieje oszacowanie górne liczby niezależności wierzchołkowej w grafie prostym, to znaczy mocy największego zbioru niezależnego? Oczywiście liczba niezależności nie przekroczy liczby wierzchołków grafu, ale czy można chociaż troszkę lepiej to oszacować, np za pomocą krawędzi w grafie albo sumy stopni pewnych wierzchołków? Będę wdzięczny za wszelkie informacje i z góry dziękuję.