4 zadania - grafy.

[anitalochowicz]

Witam!
Wszystkich mam 4 zadania do policzenia, szybko potrzebuje pomocy, bo termin oddania ich już mi się kończy. Pozdrawiam

Zadanie 1

Pokazać, że jeżeli każda krawędź grafu K6 jest pokolorowana na czerwono lub zielono, to będą istniały co najmniej dwa jednokolorowe podgrafy K3. Pokazać ,ze jeżeli K7 jest pokolorowany w ten sposób, to będą istniały co najmniej trzy jednokolorowe podgrafy K3.

Zadanie 2
Dla danych dwóch grafów G1 = (V,E1) i G2 = (V,E2) niech G1 U G2 będzie grafem (V,E1 U E2). Pokazać , że
χ (G1 U G2) ≤ χ(G1) � χ (G2)
gdzie, jak zwykle, χ(G) oznacza minimalna ilość kolorów, potrzebną do pokolorowania wierzchołków grafu G.
Wywnioskować, że jeżeli G = (V,E) jest grafem, którego dopełnienie jest planarne, to χ(G)≥|V| /5 .
Zadanie 3
(i) Pokazać, że suma liczb stojących r – tym rzędzie „trójkąta”, przedstawionego poniżej, wynosi {r+1 2}
i, korzystając z tego, wyrazić sumę wszystkich liczb zawartych w „trójkącie” w postaci współczynnika dwumianowego.

1
1 2
1 2 3 4
..
1 2 3 4 n




ii)Sumując na różne sposoby liczby stojące w „trójkącie” wywnioskować, że


rysunek: trójkąt który dzieli się na na małe trójkąty w podstawie jest ich 9, przechodząc do wierzchołka trójkąta małe trójkąty w trójkącie maleją o 2 trójkąty aż do jednego trójkąta w wierzchołku.



Zadanie 4
Na ile sposobów można pomalować
(1) wierzchołki,
(2) krawędzie,
zamieszczonego poniżej grafu dwoma kolorami ?
rysunek :znak większości kreska znak mniejszości i połączone są te wszystkie elementy ze sobą

"Dyskretna -szybka osoba do zadań potrzebna" Na przyszłość odradzam takich tematów.
Kasia