Potrzebuję formalnego rozwiązania zadania przy pomocy indukcji matematycznej:
"Niech \(\displaystyle{ G}\) będzie grafem rzędu \(\displaystyle{ n \ge 3}\). Udowodnij indukcyjnie, że jeżeli \(\displaystyle{ ||G|| \ge \left\lfloor \frac{ n^{2} }{4} \right\rfloor +1}\), to w grafie \(\displaystyle{ G}\) istnieje podgraf \(\displaystyle{ K_{3}.}\)"
Z góry dziękuję za wszelką pomoc.
Indukcja matematyczna w grafie.
-
- Użytkownik
- Posty: 21
- Rejestracja: 12 sty 2018, o 16:27
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 15 razy
Indukcja matematyczna w grafie.
Ostatnio zmieniony 26 kwie 2018, o 21:27 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
-
- Użytkownik
- Posty: 1114
- Rejestracja: 26 paź 2008, o 19:43
- Płeć: Mężczyzna
- Podziękował: 23 razy
- Pomógł: 157 razy
Indukcja matematyczna w grafie.
To jest, bardzo znane, twierdzenie Mantela. Tego jest pełno w internecie. A jeszcze więcej jak wpiszesz Mantel theorem po angielsku.
, zad. 7
37 OM - III - 5: [url]http://archom.ptm.org.pl/?q=node/789[/url]
Btw. Istnieje wiele dowodów tego twierdzenia, nie tylko indukcyjny.
, zad. 7
Kod: Zaznacz cały
http://www.deltami.edu.pl/temat/matematyka/teoria_grafow/2010/04/27/Rapsodia_pajecza/
37 OM - III - 5: [url]http://archom.ptm.org.pl/?q=node/789[/url]
Btw. Istnieje wiele dowodów tego twierdzenia, nie tylko indukcyjny.