szukanie zaawansowane
 [ Posty: 5 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 28 wrz 2014, o 09:29 
Użytkownik

Posty: 394
Lokalizacja: Warszawa
Witam,mam takie zadanie.
Mamy graf o p\ge6 wierzchołkach. Wykazać,że ma cykl hamiltona jeżeli każdy jego podgraf indukowany przez 4 wierzchołki ma 4 krawędzie.

-- 29 wrz 2014, o 18:21 --

Naprawdę nikt nie ma pomysłu na to zadanie? Nie proszę o rozwiązanie tylko jakąś wskazówkę,sposób postępowania.
Góra
PostNapisane: 30 wrz 2014, o 12:08 
Użytkownik
Pokaż, że ten graf nie zawiera "theta podgrafu".
Góra
Mężczyzna Offline
PostNapisane: 2 paź 2014, o 18:33 
Użytkownik

Posty: 394
Lokalizacja: Warszawa
Ale skąd wiem,że on jest dwuspójny? Myślę,że to zły pomysł,bo nie wiem z jakim grafem mam do czynienia
Góra
PostNapisane: 3 paź 2014, o 09:48 
Użytkownik
Usuwając dowolny wierzchołek usuwamy tylko krawędzie o końcach w w tym wierzchołku. Usuńmy zatem jakiś wierzchołek w z grafu G. Weźmy zatem dowolne dwa wierzchołki u,v\in G\setminus \{w\} i dobierzmy jeszcze dwa inne wierchołki s,t\in G\setminus\{w\}. Graf indukowany w G\setminus \{w\} przez u,v,s,t jest taki sam jak graf indukowany przez u,v,s,t w G zatem ma 4 krawędzie a więc jest spójny, w szcególności istnieje droga łącząca punkty u i v w grafie G\setminus \{w\} a to oznacza, że graf G jest dwuspójny.
Góra
Mężczyzna Offline
PostNapisane: 8 cze 2015, o 01:03 
Użytkownik

Posty: 394
Lokalizacja: Warszawa
Przeglądam teraz ten post i muszę go odświeżyć. Dalej nie widzę,żeby ten graf był dwuspójny: o dwuspójności znam tylko twierdzenie Airesa i że dla każdej pary wierzchołków musi istnieć cykl prosty. Może ktoś dokończyć to zadanie,ewentualnie pokazać,że ten graf jest na pewno dwuspójny?
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 5 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 zliczyć liczbę spójnych składowych w grafie dla permutacji.  matinf  2
 Wszystkie grafy nieplanarne o 6 wierzchołkach  donmaciej  2
 pary przy okrągłym stole, cykl hamiltona - zadanie 2  Pawimis  1
 Turniej a ścieżka Hamiltona  Rudis  4
 Wykaż,że graf planarny o n wierzchołkach ma  zuzka_kotek  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl