Teoria Grafów.

[frania12]

Witam. Proszę kogoś o pomoc w kilku zadaniach. Muszę je mieć na jutro zrobione. Z góry dziękuję za pomoc.

1. Uzasadnij, ze kazdy graf prosty rzedu co najmniej dwa zawiera dwa wierzcholki tego samego stopnia.

2. Wykazać, że istnieją dokładnie cztery parami nieizomorficzne grafy proste rzedu trzy i jedenascie rzedu cztery. Ile jest takich grafow rzedu piec ?

3. Wykazac, ze istnieje graf G (niekoniecznie prosty) taki, _ze D(G) = (5; 5; 5; 3; 3; 3). Czy istnieje
graf prosty o takim ciagu stopni ?

4. Grafem krawedziowym L(G) grafu prostego G nazywamy graf, ktorego zbiorem wierzcholkow
jest zbior krawedzi grafu G i dwa wierzcho lki grafu L(G) sa w nim polaczone wtedy i tylko wtedy, gdy odpowiadajace nim krawedzie grafu G sa sasiednie w G. Znalezc wyrazenie opisujace ilosc krawedzi grafu L(G) w zale_znosci od stopni grafu G.

5. Dopelnieniem Gc grafu prostego G nazywamy graf o tym samym zbiorze wierzcho lkow co G lecz
w ktorym wierzcholki sa polaczone wtedy i tylko wtedy, gdy nie sa polaczone w G. Znalezc graf G taki, ze Gc ' G (tzw. graf samodopelniajacy). Wykazac, ze jesli G jest somodopelniajacym sie grafem prostym, to v(G) przystaje do 0 modulo 4 lub v(G) przystaje do 1 modulo 4.

6. Para polstopni wierzcholka x w grafie skierowanym G nazywamy pare (d+G(x); d G(x)). Graf
skierowany G = (V;E) nazywamy przciwregularnym, jesli dla dowolnych x; y 2 V zachodzi implikacja
x 6= y ) (d+
G(x); d
G(x)) 6= (d+
G(y); d
G(y)):
Znalezc grafy przeciwregularne rzedu 3, 4 oraz 5. Czy istnieje graf przeciwregularny dowolnego
rzedu n, n >=1 ?

7. Niech G bedzie grafem, ktorego zbior wierzcholkow stanowia komputery, ktore moga sie laczyc z soba bezprzewodowo, jesli polozone sa w odleglosci nie wiekszej ni_z ustalona jednostka d (np. 500m), wtedy wierzcholki sa polaczone w G. Czy jest mozliwe aby taki graf byl cyklem dlugosci 3, 4, 5 ? Czy musi to byc graf spojny ? Czy jest mozliwe aby taki graf byl gwiazda K1, n, n>=3, t.j. grafem prostym, w ktorym dokladnie jeden wierzcholek jest po laczony z wszystkimi pozostalymi a pozostał wierzcholki sa stopnia 1?

8. Graf nieskierowany bez krawedzi wielokrotnych, w ktorym moga wystepowac petle nazywamy przeciwregularnym, jesli jego rozne wierzcholki maja rozne stopnie. Podaj przyklady takich grafow rzedu 3, 4 oraz 5. Jaki musi byc ciag (zbior) stopni takiego grafu rzedu n ? Jaka jest najmniejsz ilosc petli w takim grafie rzedu n?




Bardzo bym prosił o pomoc w tych zadaniach.
Tutaj dodatkowo dodaję linka do pdf: http://moodle.math.uni.opole.pl/moodle/ ... ys_7_2.pdf