zad egz grafy, Studia WIT - Informatyka, MDA - Matematyka dyskretna
[ Pobierz całość w formacie PDF ]
//-->Przykładowe zadania egzaminacyjne z teorii grafówLp. Zadanie1. Wyjaśnij w oparciu o tw. Halla, dlaczego w grafie podanym na rysunku niema skojarzenia pełnego względem zbioru V1= {1, 2, 3, 4, 5}.678910123452. W podanej sieci (przy jej łukach podano przepustowości) znane sąnastępujące przepływy:f(v,s)= 1,f(s,y)= 3,f(v,y)= 1,f(z,x)= 0,f(z,t)= 1,f(x,t)= 3.Wyznacz przepływy w pozostałych łukach tak, aby został w siecizdefiniowany przepływ zsdot.Wyznacz wartość przepływu przez całą sieć i wartość przepływu przezprzekrój zadany zbiorem węzłów {s,v, y}.W oparciu o tw. Forda i Fulkersona rozstrzygnij, czy uzyskany przepływ jestmaksymalny w tej sieci.x6s2v13y233132t3. W pewnym kraju Unii Europejskiej jest 9 dużych miast. Pomiędzy każdą parą miast zbudowana jest wygodna autostrada.Rolnicy tego kraju, niezadowoleni z wysokości dopłat bezpośrednich, postanowili zablokować te autostrady wysypując nanie efekty swojej pracy. Jednak płodów rolnych starczyło im tylko na zablokowanie po jednym kierunku ruchu z każdejautostrady. Rozstrzygnij z uzasadnieniem, czy premier tego kraju będzie mógł odwiedzić samochodem, nie łamiącprzepisów ruchu drogowego, wszystkie duże miasta, zaczynając podróż z dowolnego i odwiedzając każde tylko raz. Czymoże być pewny,żewróci do miasta, z którego wyruszy?4. W grafie pokazanym na rysunku zaznaczono skojarzenie (krawędziepogrubione). Za pomocą kolejnych dróg powiększających względemskojarzenia wyznacz w tym grafie skojarzenie maksymalne.Czy wyznaczone skojarzenie jest doskonałe? Odpowiedzi uzasadnij.Wskaż w grafie jakiekolwiek minimalne pokrycie krawędziowe.Podaj ogólny związek liczby elementów w wyznaczonym skojarzeniui pokryciu.5. Podaj, które z grafów pokazanych na rysunkachsą ze sobą izomorficzne, a które nie są.G1G21471025811369G5G3G4G66. Rozważ graf o liczbie wierzchołkówn≥3 i jego dopełnienie. Wyprowadź i podaj warunek dla stopni wierzchołków wgrafie, który zapewni,żew dopełnieniu tego grafu będzie spełniony warunek dostateczny istnienia cyklu Hamiltona ztw. Ore.7. Rozstrzygnij z uzasadnieniem prawdziwość następujących stwierdzeń:1. Jeżeli w grafie G istnieje cykl Eulera, to w grafie krawędziowym L(G) także istnieje cykl Eulera.2. Jeżeli w grafie krawędziowym L(G) istnieje cykl Eulera, to w grafie G także istnieje cykl Eulera.8. Rozstrzygnij z uzasadnieniem, czy graf, którego zbiorem wierzchołków jest zbiór kodów Graya rzędu 3, a krawędziełączą dwa kody różniące się dokładnie na jednej pozycji, jest grafem dwudzielnym.agd9. W podanym grafie wyznacz:a) maksymalną liczbę dróg krawędziowo rozłącznych pomiędzy parąwierzchołków v i w,vbehb) minimalny zbiór krawędzi rozspajający te wierzchołki.Zilustruj krawędziową wersję tw. Mengera na powyższych zbiorach.Rozstrzygnij z uzasadnieniem, czy ten graf jest 4-spójny krawędziowo?cfjw10. Czy dla grafu o 9 wierzchołkach, w którym suma stopni wierzchołków wynosi 58 jego dopełnienie może być grafemspójnym? Odpowiedź dokładnie uzasadnij bez konstruowania i rysowania grafu.
[ Pobierz całość w formacie PDF ]