szukanie zaawansowane
 [ Posty: 5 ] 
Autor Wiadomość
PostNapisane: 28 wrz 2014, o 08:29 
Użytkownik
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 11:08 
Użytkownik
Pokaż, że ten graf nie zawiera "theta podgrafu".
Góra
PostNapisane: 2 paź 2014, o 17:33 
Użytkownik
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 08: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
PostNapisane: 8 cze 2015, o 00:03 
Użytkownik
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 
 cykle w grafie. kiedy występuje cykl?  magicolandia  1
 Cykle i przekroje w grafie  jpxx  0
 Ile jest wszystkich drzew rozpiętych na n wierzchołkach...  PanTy  1
 W grafie 2-spójnym każde dwa wierzchołki należą do cyklu  rafalpw  0
 Cykl Hamiltona gdy go byc nie powinno  filip.wroc  4
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl