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ź?
Graf samodopełniający
-
- Użytkownik
- Posty: 97
- Rejestracja: 14 sty 2014, o 19:35
- Płeć: Kobieta
- Lokalizacja: Lublin
- Podziękował: 7 razy
-
- 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
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.
Q.