Graf samodopełniający

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
gosiak5321
Użytkownik
Użytkownik
Posty: 97
Rejestracja: 14 sty 2014, o 19:35
Płeć: Kobieta
Lokalizacja: Lublin
Podziękował: 7 razy

Graf samodopełniający

Post autor: gosiak5321 »

Graf \(\displaystyle{ G}\) nazywamy samodopełniającym wtedy i tylko wtedy, gdy graf \(\displaystyle{ G}\) jest izomorficzny z \(\displaystyle{ \overline{G}}\). Uzasadnić, że jeśli graf jest samodopoełniający, to ma \(\displaystyle{ 4k}\) lub \(\displaystyle{ 4k+1}\) wierzchołków.

Może jakaś podpowiedź?
Użytkownik
Użytkownik
Posty: 9833
Rejestracja: 18 gru 2007, o 03:54
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 90 razy
Pomógł: 2632 razy

Graf samodopełniający

Post autor: »

Graf \(\displaystyle{ G\cup \overline{G}}\) jest grafem pełnym, czyli jeśli liczba wierzchołków grafu \(\displaystyle{ G}\) (i grafu \(\displaystyle{ \overline{G}}\)) to \(\displaystyle{ n}\), to graf \(\displaystyle{ G\cup \overline{G}}\) ma \(\displaystyle{ \binom n2 = \frac{n(n-1)}{2}}\) krawędzi. Ale grafy \(\displaystyle{ G}\) i \(\displaystyle{ \overline{G}}\) mają tyle samo krawędzi jako grafy izomorficzne. Stąd liczba \(\displaystyle{ \frac{n(n-1)}{2}}\) musi być parzysta, a stąd łatwo wynika teza.

Q.
ODPOWIEDZ