Liczba krawędzi w dopełnieniu grafu regularnego

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
stefan13
Użytkownik
Użytkownik
Posty: 150
Rejestracja: 11 cze 2014, o 21:33
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 41 razy

Liczba krawędzi w dopełnieniu grafu regularnego

Post autor: stefan13 »

Czy jest jakiś wzór, sposób na szybkie obliczenie liczby krawędzi w dopełnieniu grafu regularnego, prostego?
Graf powiedzmy, że ma 10 wierzchołków i 15 krawędzi.

Według mnie wynik to 30, aczkolwiek według odpowiedzi jest 35
Mruczek
Użytkownik
Użytkownik
Posty: 1114
Rejestracja: 26 paź 2008, o 19:43
Płeć: Mężczyzna
Podziękował: 23 razy
Pomógł: 157 razy

Re: Liczba krawędzi w dopełnieniu grafu regularnego

Post autor: Mruczek »

To nie ma znaczenia, czy jest regularny, czy nie. Ważniejsze, że jest prosty - nie ma pętli i krawędzi wielokrotnych.
W klice \(\displaystyle{ 10}\) wierzchołkowej jest \(\displaystyle{ {10 \choose 2} =45}\) krawędzi. Tutaj jest \(\displaystyle{ 15}\) krawędzi, więc w dopełnieniu jest \(\displaystyle{ 45 - 15 = 30}\) krawędzi. W odpowiedziach chyba się pomylili.
ODPOWIEDZ