[ Pobierz całość w formacie PDF ]
.ÿþMatematyka dyskretnaDr Marek ZakrzewskiWykÅ‚ad 07Teoria grafówCo zrobić, żeby koniki z pól 1 i 7 przeszÅ‚y na 3 i 5 i na odwrót?Każdy konik musi wykonać 4 ruchy w kierunku zgodnym zruchem wskazówek zegara.Zadanie Alcuina o wilku, kozie i kapuÅ›cie (=saÅ‚acie).Należy przeprawić wilka, kozÄ™ i saÅ‚atÄ™na drugi brzeg rzeki wiedzÄ…c, że w łódce może znajdować siÄ™ naraz tylko jedno z nich i najednym brzegu bez opieki nie mogÄ… zostać równoczeÅ›nie wilk i koza, ani koza i saÅ‚ata.Podstawowe terminy podstawowe przykÅ‚adyG=„àV , E…à G - graf, - wierzchoÅ‚ki (vertices), - krawÄ™dzie (edges)V EPrzyjmiemy umowÄ™, że krawÄ™dzie nie majÄ… kierunku, tzn.krawÄ™dz jest parÄ… wierzchoÅ‚ków(nieuporzÄ…dkowanÄ…).{V , V }Zazwyczaj przyjmujemy też, że nie ma pÄ™tli, tzn krawÄ™dzi typu.Graf zwykÅ‚y to graf symetryczny (krawÄ™dzie nie majÄ… kierunku), bez pÄ™tli i bez krawÄ™dziwielokrotnych.StopieÅ„ wierzchoÅ‚ka to ilość krawÄ™dzi wychodzÄ…cych z danego wierzchoÅ‚ka.Lemat o uÅ›ciskach dÅ‚onist v1ƒàst v ƒà.ƒàst vk=2#"E#"2Graf nazywamy regularnym, jeżeli wszystkie wierzchoÅ‚ki majÄ… ten sam stopieÅ„.K- graf peÅ‚ny (Kuratowski)nCn - grafy cykliczne Grafy platoÅ„skie (=szkielety krawÄ™dziowe wieloÅ›cianów foremnych)Graf PetersenaMapa Królewca (1736)Graf nazywamy eulerowskim jeżeli istnieje w nim cykl Eulera, tzn.cykl przechodzÄ…cydokÅ‚adnie raz przez każdÄ… krawÄ™dz.Twierdzenie (Eulera-Hierholzera)Graf spójny jest eulerowski wtedy i tylko wtedy, gdy stopieÅ„ każdego wierzchoÅ‚ka jestparzysty.Dowód (szkic)Oczywiste, bo jeÅ›li do wierzchoÅ‚ka wchodzimy to musimy z niego wyjść.Z parzystoÅ›ci stopni wierzchoÅ‚ków wynika, że istnieje jakiÅ› cykl (bez powtórzeÅ„).Rozważmy najdÅ‚uższy cykl.Przypuśćmy, że nie zawiera on wszystkich krawÄ™dzi, tzn.istniejekrawÄ™dz poza cyklem.Ze spójnoÅ›ci można przyjąć, że krawÄ™dz ta styka siÄ™ z cyklem.Niechv punkt cyklu leżący na tej dodatkowej krawÄ™dzi.ZaczynajÄ…c od tej krawÄ™dzi zbudujemycykl (krawÄ™dziowo) rozÅ‚Ä…czny z cyklem danym.WyjÅ›ciowy cykl można uzupeÅ‚nić tymnowym cyklem wbrew zaÅ‚ożeniom maksymalnoÅ›ci.SprzecznośćGraf nazywamy hamiltonowskim, jeÅ›li istnieje w nim cykl Hamiltona,tzn.cykl przechodzÄ…cy dokÅ‚adnie raz przez każdy wierzchoÅ‚ek. Twierdzenie Diraca (1952)nst žàv Ÿàe"nJeżeli ( - liczba wierzchoÅ‚ków grafu), to graf jest hamiltonowski.2DowódZałóżmy, że twierdzenie jest faÅ‚szywe, tzn.istnieje graf speÅ‚niajÄ…cyto zaÅ‚ożenie, ale niehamiltonowski.JeÅ›li trzeba dodajemy trochÄ™krawÄ™dzi, tak aby otrzymać maksymalny graf niehamiltonowski.Wu=v1 v2 v3.vn=wtakim grafie istnieje droga Hamiltona.v1 viƒà1iNiech A - zbiór tych indeksów , że sÄ…siaduje z.vi vnBPodobnie - zbiór tych indeksów i , że sÄ…siaduje z.n n#"A#"d" , #"B#"d"I ={1,2 ,., n-1}Niech.Wówczas A"I , B"I , a ponieważ , to2 2v1 viƒà1 viƒà2.v vi vi-1.v1istnieje i"A)"B.Wówczas jest cyklem hamiltona.nSprzeczność."000 12 1234{a}100 21 123 1343{a,b}110 132 1423{b}010 312 4123{b,c}011 321 4132{a,b,c}111 231 1432{a,c}101 213 1342{c}001 123 1324"000 31243142.Ile jest różnych grafów zwykÅ‚ych o wierzchoÅ‚kach 1,2,.,n?nnžà Ÿà2KrawÄ™dzi możliwych jest czyli grafów jest.žà Ÿà22Izomorfizm (izo=równe,morf=ksztaÅ‚t)1-1G2=žàV , E2Ÿà f : V Œà VGraf oraz sÄ… izomorficzne, jeżeli istnieje sÄ…siednie wtedy i2 1 2naf žàV Ÿà , f žàV Ÿàtylko wtedy, gdy sÄ…siednie.1 2f žà1Ÿà=2f žà2Ÿà=1f žà3Ÿà=3 [ Pobierz caÅ‚ość w formacie PDF ]
zanotowane.pl doc.pisz.pl pdf.pisz.pl matkasanepid.xlx.pl
.ÿþMatematyka dyskretnaDr Marek ZakrzewskiWykÅ‚ad 07Teoria grafówCo zrobić, żeby koniki z pól 1 i 7 przeszÅ‚y na 3 i 5 i na odwrót?Każdy konik musi wykonać 4 ruchy w kierunku zgodnym zruchem wskazówek zegara.Zadanie Alcuina o wilku, kozie i kapuÅ›cie (=saÅ‚acie).Należy przeprawić wilka, kozÄ™ i saÅ‚atÄ™na drugi brzeg rzeki wiedzÄ…c, że w łódce może znajdować siÄ™ naraz tylko jedno z nich i najednym brzegu bez opieki nie mogÄ… zostać równoczeÅ›nie wilk i koza, ani koza i saÅ‚ata.Podstawowe terminy podstawowe przykÅ‚adyG=„àV , E…à G - graf, - wierzchoÅ‚ki (vertices), - krawÄ™dzie (edges)V EPrzyjmiemy umowÄ™, że krawÄ™dzie nie majÄ… kierunku, tzn.krawÄ™dz jest parÄ… wierzchoÅ‚ków(nieuporzÄ…dkowanÄ…).{V , V }Zazwyczaj przyjmujemy też, że nie ma pÄ™tli, tzn krawÄ™dzi typu.Graf zwykÅ‚y to graf symetryczny (krawÄ™dzie nie majÄ… kierunku), bez pÄ™tli i bez krawÄ™dziwielokrotnych.StopieÅ„ wierzchoÅ‚ka to ilość krawÄ™dzi wychodzÄ…cych z danego wierzchoÅ‚ka.Lemat o uÅ›ciskach dÅ‚onist v1ƒàst v ƒà.ƒàst vk=2#"E#"2Graf nazywamy regularnym, jeżeli wszystkie wierzchoÅ‚ki majÄ… ten sam stopieÅ„.K- graf peÅ‚ny (Kuratowski)nCn - grafy cykliczne Grafy platoÅ„skie (=szkielety krawÄ™dziowe wieloÅ›cianów foremnych)Graf PetersenaMapa Królewca (1736)Graf nazywamy eulerowskim jeżeli istnieje w nim cykl Eulera, tzn.cykl przechodzÄ…cydokÅ‚adnie raz przez każdÄ… krawÄ™dz.Twierdzenie (Eulera-Hierholzera)Graf spójny jest eulerowski wtedy i tylko wtedy, gdy stopieÅ„ każdego wierzchoÅ‚ka jestparzysty.Dowód (szkic)Oczywiste, bo jeÅ›li do wierzchoÅ‚ka wchodzimy to musimy z niego wyjść.Z parzystoÅ›ci stopni wierzchoÅ‚ków wynika, że istnieje jakiÅ› cykl (bez powtórzeÅ„).Rozważmy najdÅ‚uższy cykl.Przypuśćmy, że nie zawiera on wszystkich krawÄ™dzi, tzn.istniejekrawÄ™dz poza cyklem.Ze spójnoÅ›ci można przyjąć, że krawÄ™dz ta styka siÄ™ z cyklem.Niechv punkt cyklu leżący na tej dodatkowej krawÄ™dzi.ZaczynajÄ…c od tej krawÄ™dzi zbudujemycykl (krawÄ™dziowo) rozÅ‚Ä…czny z cyklem danym.WyjÅ›ciowy cykl można uzupeÅ‚nić tymnowym cyklem wbrew zaÅ‚ożeniom maksymalnoÅ›ci.SprzecznośćGraf nazywamy hamiltonowskim, jeÅ›li istnieje w nim cykl Hamiltona,tzn.cykl przechodzÄ…cy dokÅ‚adnie raz przez każdy wierzchoÅ‚ek. Twierdzenie Diraca (1952)nst žàv Ÿàe"nJeżeli ( - liczba wierzchoÅ‚ków grafu), to graf jest hamiltonowski.2DowódZałóżmy, że twierdzenie jest faÅ‚szywe, tzn.istnieje graf speÅ‚niajÄ…cyto zaÅ‚ożenie, ale niehamiltonowski.JeÅ›li trzeba dodajemy trochÄ™krawÄ™dzi, tak aby otrzymać maksymalny graf niehamiltonowski.Wu=v1 v2 v3.vn=wtakim grafie istnieje droga Hamiltona.v1 viƒà1iNiech A - zbiór tych indeksów , że sÄ…siaduje z.vi vnBPodobnie - zbiór tych indeksów i , że sÄ…siaduje z.n n#"A#"d" , #"B#"d"I ={1,2 ,., n-1}Niech.Wówczas A"I , B"I , a ponieważ , to2 2v1 viƒà1 viƒà2.v vi vi-1.v1istnieje i"A)"B.Wówczas jest cyklem hamiltona.nSprzeczność."000 12 1234{a}100 21 123 1343{a,b}110 132 1423{b}010 312 4123{b,c}011 321 4132{a,b,c}111 231 1432{a,c}101 213 1342{c}001 123 1324"000 31243142.Ile jest różnych grafów zwykÅ‚ych o wierzchoÅ‚kach 1,2,.,n?nnžà Ÿà2KrawÄ™dzi możliwych jest czyli grafów jest.žà Ÿà22Izomorfizm (izo=równe,morf=ksztaÅ‚t)1-1G2=žàV , E2Ÿà f : V Œà VGraf oraz sÄ… izomorficzne, jeżeli istnieje sÄ…siednie wtedy i2 1 2naf žàV Ÿà , f žàV Ÿàtylko wtedy, gdy sÄ…siednie.1 2f žà1Ÿà=2f žà2Ÿà=1f žà3Ÿà=3 [ Pobierz caÅ‚ość w formacie PDF ]