Matematyka dyskretna, zadanie nr 1409

Autor	Zadanie / Rozwiązanie
marc1234 postów: 4	2013-06-08 16:07:03 Witam, proszę o sprawdzenie zadań z teorii grafów i o podanie prawidłowych odpowiedzi tam, gdzie mam błędy albo chociaż o wskazówki jak je zrobić. Z góry dziękuję za pomoc :) Zadania: 1. Ile krawędzi ma 3-regularny graf o 100 wierzchołkach? a) 200 b) 300 c) 150 d) nie istnieje taki graf Wybrałem: C 2. Pewien $k$-regularny graf o 20 wierzchołkach ma 200 krawędzi. Ile wynosi $k$? a) 10 b) 20 c) nie istnieje taki graf d) 40 Wybrałem: B 3. Ile krawędzi ma 5-regularny graf o 75 wierzchołkach? a) inna odpowiedź b) 750 c) 375 D) nie istnieje taki graf Wybrałem: D 4. Mucha chodzi po krawędziach wielościanu foremnego. Okazało się, że obeszła wszystkie krawędzie, przechodząc po każdej dokładnie jeden raz. Jaki to mógł być wielościan? (może być kilka odpowiedzi) a) sześcian b) dwunastościan c) dwudziestościan d) czworościan e) ośmiościan Wybrałem: E 5. Graf pełny $K_{n}$ ma obwód Eulera. Co można powiedzieć o $n$? (może być kilka odpowiedzi) a) daje resztę 1 przy dzieleniu przez 4 b) jest podzielne przez 4 c) jest nieparzyste d) jest parzyste Wybrałem: C 6. Graf $G$ jest najmniejszym (w sensie liczby krawędzi) grafem o n wierzchołkach, który zawiera obwód Eulera. Ile krawędzi ma $G$? a) $n+1$ b) $n-1$ c) $n$ d) inna odpowiedź Wybrałem: C 7. Grafem pełnym dwudzielnym $K_{m,n}$ nazywamy graf, którego zbiór wierzchołków można podzielić na dwa rozłączne podzbiory $X$, $Y$ takie, że $\|X\|=n$ oraz $\|Y\|=m$. Krawędzie łączą każdy wierzchołek z $X$ z każdym wierzchołkiem z $Y$ (nie ma krawędzi pomiędzy dwoma wierzchołkami z tego samego podzbioru). Wskaż grafy, które mają drogę Eulera. (może być kilka odpowiedzi) a) $K_{6,10}$ b) $K_{8,8}$ c) $K_{1,2}$ d) $K_{2,3}$ Wybrałem: A, B 8. Dany jest graf. Wskaż zdanie prawdziwe: a) Narysowany graf nie ma ani drogi Eulera, ani obwodu Eulera. b) Narysowany graf ma drogę Eulera, ale nie ma obwodu Eulera. c) Narysowany graf ma obwód Eulera. Wybrałem: A 9. Dany jest graf. Wskaż zdanie prawdziwe: a) Narysowany graf nie ma ani drogi Eulera, ani obwodu Eulera. b) Narysowany graf ma drogę Eulera, ale nie ma obwodu Eulera. c) Narysowany graf ma obwód Eulera. Wybrałem: C 10. Wskaż zdania prawdziwe (może być kilka odpowiedzi): a) Jeśli graf $G$ jest niespójny, nie ma w nim drogi zamkniętej zawierającej wszystkie krawędzie. b) $G$ jest grafem spójnym o wszystkich stopniach parzystych. Wtedy $G$ ma dokładnie jeden obwód Eulera. c) $G$ jest grafem spójnym o dokładnie dwóch wierzchołkach stopnia nieparzystego. Wtedy $G$ ma dokładnie jedną drogę Eulera. d) $G$ jest grafem spójnym o co najwyżej dwóch wierzchołkach stopnia nieparzystego. Wtedy $G$ ma dokładnie jedną drogę Eulera. Wybrałem: A

tumor postów: 8070	2014-05-31 18:12:35 1. Graf $3$-regularny to taki, w którym z każdego wierzchołka wychodzą $3$ krawędzie. To daje $\frac{300}{2}$, bo każdą krawędź liczyliśmy dwukrotnie. czyli C 2. $\frac{20*k}{2}=200$, $k=20$ B

tumor postów: 8070	2014-05-31 18:12:51 3. $\frac{5*75}{2}$ nie jest całkowite, czyli $D$ 4. Wielościan foremny ma tyle samo krawędzi przy każdym wierzchołku. Najwyżej przy dwóch mógłby mieć nieparzyste ilości, by mucha mogła przejść, czyli w konsekwencji przy każdej ma parzystą ilość. Jedynym wielościanem spełniającym ten warunek jest ośmiościan. (Por. Mosty w Królewcu i Euler)

tumor postów: 8070	2014-05-31 18:28:53 5. Graf pełny o n wierzchołkach jest n-1-regularny Cykl Eulera wymaga, by n-1 było parzyste, czyli n nieparzyste. Innych warunków nie ma. 6. Zakładam, że rozważamy grafy spójne. Wówczas każdy wierzchołek ma dwie krawędzie, czyli dla n wierzchołków wystarcza n krawędzi.

strony: 1

Prawo do pisania przysługuje tylko zalogowanym użytkownikom. Zaloguj się lub zarejestruj