Zad. 1 Wykaż, że graf, w którym wszystkie stopnie są parztyste nie może posiadać mostu. Następnie dla dowolnego \(\displaystyle{ k \geq 1}\) skonstrułuj \(\displaystyle{ (2k + 1)}\)-regularny graf posiadający most.
Zad. 2 Wykaż,że jeśli graf \(\displaystyle{ G=(V,E)}\) spełnia warunek \(\displaystyle{ |E|>{|V|-1\choose 2}}\), to \(\displaystyle{ G}\) jest spójny.
Zad. 3 Wykaż, że jeżeli \(\displaystyle{ G=(V,E)}\) jest kubicznym grafem prostym, to \(\displaystyle{ \lambda (G)= \kappa (G)}\).
Jeszcze muszę rozwiazać takich zadań ponad 60, bo w poniedziałek mam kolokwium z tego.
Pomoże mi ktos??
edit:
@down - lol mądrala się znalazł, najlepiej zmienic temat, nie??? jak nie wiesz jak rozwiązać to nie nabijaj głupio-mądrych postów
3 zadania o grafach
-
półpasiec
- Gość Specjalny
- Posty: 534
- Rejestracja: 8 lip 2004, o 17:05
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 1 raz
- Pomógł: 17 razy
3 zadania o grafach
1) jesli istnieje most to od wierzcholka z jednej strony do wierzcholka z drugiej strony mostu moze prowadzic tylko jedna droga, ale skoro stopnie sa parzyste to istnieje cykl Hamiltona wiec sprzecznosc, bo istnieja co najmniej dwie drogi miedzy kazdymi wierzcholkami
konstrukcja
bierzesz krawedz i ona bedzie mostem
po kazdej stronie mostu dajesz 2k wierzcholkow, poczatek mostu z kazdej strony laczysz ze wszystkimi z tej czesci, a w samych tych czesciach laczysz kazdy z kazdym
2) zrobie dla dwoch skladowych, z wieksza iloscia pojdzie analogicznie lub przez indukcje
zalozmy ze mamy dwie skladowe w jednej \(\displaystyle{ l}\), w drugiej \(\displaystyle{ |V|-l}\) wierzcholkow, w poszczegolnych skladowych moze byc co najwyzej \(\displaystyle{ l(l-1)/2,(|V|-l)(|V|-l-1)/2}\) krawedzi, pozostaje pokazac ze \(\displaystyle{ l(l-1)/2+(|V|-l)(|V|-l-1)/2 q (|V|-1)(|V|-2)/2}\)
3) jak wytlumaczysz co to graf kubiczny to cos sie wykombinuje
konstrukcja
bierzesz krawedz i ona bedzie mostem
po kazdej stronie mostu dajesz 2k wierzcholkow, poczatek mostu z kazdej strony laczysz ze wszystkimi z tej czesci, a w samych tych czesciach laczysz kazdy z kazdym
2) zrobie dla dwoch skladowych, z wieksza iloscia pojdzie analogicznie lub przez indukcje
zalozmy ze mamy dwie skladowe w jednej \(\displaystyle{ l}\), w drugiej \(\displaystyle{ |V|-l}\) wierzcholkow, w poszczegolnych skladowych moze byc co najwyzej \(\displaystyle{ l(l-1)/2,(|V|-l)(|V|-l-1)/2}\) krawedzi, pozostaje pokazac ze \(\displaystyle{ l(l-1)/2+(|V|-l)(|V|-l-1)/2 q (|V|-1)(|V|-2)/2}\)
3) jak wytlumaczysz co to graf kubiczny to cos sie wykombinuje