201305291642

Zadanie 1.

Zadanie 2. Zadanie 3. Zadanie 4. Zadanie 5.

Zadanie 6. Zadanie 7.

MDiL 29 maja 2013

Znajdź w grafie Petersena

(a)    cykle długości 5,6,8,9

(b)    zbiór rozspajający

(c)    rozcięcia składające się z 3,4,5 krawędzi

(d)    zbiór rozdzielający

Obwodem grafu nazywamy długość najkrótszego cyklu w tym grafie. Wyznacz obwód grafu #9,#5,7,Cs,Wg,Petersena.

Udowodnij, że jeśli każdy cykl w grafie spójnym prostym ma długość parzystą to ten graf jest grafem dwudzielnym.

Udowodnij, że graf prosty i jego dopełnienie nie mogą być jednocześnie niespójne.

Wyznacz liczby \{G) oraz k(G) dla następujących grafów

(a)	graf sześcianu
(b)	graf ośmiśianu
(c)
(d)	w6
(e)	#4,7
(f)	#5
(g)	Siao

Wykaż, że jeśli graf jest spójny i minimalny stopień wierzchołka wynosi k to X(G) < k. Narysuj graf G w którym minimalny stopień wierzchołka wynosi 4 oraz k(G) < A(G) < 4.

Które z następujących grafów są eulerowskie (hamiltonowskie). Które są półeulerowskie (półhamiltonowskie)?

(a)    #₅

(b)    #2,3

1