Matematyka dyskretna, zadanie nr 1409
ostatnie wiadomo艣ci | regulamin | latex
| Autor | Zadanie / Rozwi膮zanie |
marc1234 post贸w: 4 |  2013-06-08 16:07:03Witam, 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