zad-MD-2015-I-9, ISI UWM, Semestr II, Matematyka dyskretna
[ Pobierz całość w formacie PDF ]
//-->Olsztyn, dn. 20.05.2014 r.Matematyka dyskretna, seria 9(podstawy teorii grafów)Narysuj grafy, wyznacz ich macierze s¡siedztwa oraz grafy dopeªniaj¡ce:a) graf peªnyK6;b) graf peªny dwudzielnyK2,4;c) sum¦ grafówK1,3iW4;d) graf sze±cianu (kostk¦Q3).Zad 1.Zad 2.Zad 3.Narysowa¢ grafy bryª plato«skich.Wyznaczy¢ grafGmaj¡cy podan¡ poni»ej macierz s¡siedztwa1M=12111112111.Zad 4.Wykaza¢ izomorzm poni»szych grafów.C3H8.Zad 5.a) Narysowa¢ grafy odpowiadaj¡ce cz¡steczkom metanuCH4i propanub) Istniej¡ dwa ró»ne w¦glowodory maj¡ce wzór sumarycznyC4H10. Narysujgrafy odpowiadaj¡ce ich cz¡stkom.Narysuj wszystkie grafy proste oznakowane maj¡ce cztery wierzchoªki.Ile jest takich grafów nieoznakowanych?Zad 6.Zad 7.Sprawdzi¢, »ek-kostkaQkma2kwierzchoªków,k·2k−1kraw¦dzi orazjest grafem regularnym stopniak.a)b)c)d)e)Na rysunku powy»ej s¡ podane grafy3-regularne o o±miu wierzchoªkach.Sprawdzi¢, »e »adne dwa nie s¡ izomorczne.Zad 8.Graf prosty izomorczny ze swoim dopeªnieniem nazywamygrafem sa-modopeªniaj¡cym. Udowodnij, »e grafy dopeªniaj¡ce maj¡4klub4k + 1wierz-choªków (k∈N). Podaj przykªady grafów samodopeªniaj¡cych maj¡cych4lub5wierzchoªków.Zad 9.NiechGb¦dzie grafem prostym z co najmniej dwoma wierzchoªkami.Wyka», »eGzawiera dwa wierzchoªki tego samego stopnia.Wsk:Skorzystaj z zasady szufadkowej Dirichleta.Zad 10.
[ Pobierz całość w formacie PDF ]