W-Grafy.pdf

(1179 KB) Pobierz
Microsoft PowerPoint - wprowadzenie
1
Poj cie grafu
Def. Graf prosty G =( V , E ) jest uporz dkowan par dwóch elementów:
zbioru wierzchołków V oraz zbioru kraw dzi E Ì V ´ V . Kraw d pomi dzy
wierzchołkami u oraz v oznaczamy { u,v }. Graf prosty nie zawiera kraw dzi
postaci { u,u } oraz pomi dzy ka d par wierzchołków istnieje co najwy ej
jedna kraw d .
Def. Wierzchołki u i v s s siednie , gdy { u , v E ( G ). Wierzchołek u
oraz kraw d e s incydentne , gdy u Î e .
Przykład:
v 1
v 4
G = ( { v 1 , v 2 , v 3 , v 4 },
v 2
v 3
{ { v 1 , v 2 }, { v 2 , v 3 }, { v 3 , v 4 }, { v 4 , v 1 },{ v 2 , v 4 } } )
Uwaga. Rysunek grafu jest reprezentacj zbioru wierzchołków oraz
sposobu ich poł czenia, wi c jego własno ci metryczne nie s istotne.
10572512.001.png 10572512.002.png
2
Multigrafy oraz grafy skierowane
Def. Multigraf to graf, w którym pomi dzy dowoln par wierzchołków
mo e wyst pi wi cej ni jedna kraw d oraz dopuszczalne s p tle , tzn.
kraw dzie postaci { v,v }, gdzie v Î V ( G ) .
Def. Graf nazywamy digrafem ( grafem skierowanym ), gdy kraw d
ł cz ca u oraz v jest uporz dkowan par postaci ( u , v ).
Przykład:
u
v
u
v
w
x
w
x
G = ( { u , v , w , x },
{{ u , v }, { w , v }, { w , w }, { w , x },
{ w , x }, { w , x }, { x , v }, { x , v }} )
D = ( { u , v , w , x },
{( u , v ), ( w , v ), ( v , x ), ( x , w )} )
10572512.003.png
3
Stopie wierzchołka
Def. Stopie wierzchołka v jest oznaczany symbolem deg( v ) i jest
to ilo wierzchołków s siednich z v . Dla danego grafu G
definiujemy parametry:
d = min { deg( v ) : v Î V ( G ) }
D = max { deg( v ) : v Î V ( G ) }
Lemat o u ciskach dłoni. Niech G b dzie grafem prostym. Wówczas
deg( v 1 ) + ... + deg( v n ) = 2 m .
Dowód: (indukcja ze wzgl du na liczb kraw dzi grafu)
1. Je li m = 0, to równo jest prawdziwa.
2. Zakładamy, e lemat zachodzi dla pewnego m ³ 0.
3. Udowodnimy równanie dla m + 1. Niech e Î E ( G ) b dzie dowoln
kraw dzi . Z zało enia indukcyjnego wiadomo, e
deg( v 1 ) + ... + deg( v n ) = 2 m ( G e ),
gdzie deg( v i ) jest stopniem v i w grafie G e . Dla grafu G suma stopni
wierzchołków jest o 2 wi ksza ni dla G e oraz m ( G ) = m ( G – e ) + 1,
co oznacza, e równanie zachodzi dla grafu G o m + 1 kraw dziach.
4
Twierdzenie Havla
Tw. Ilo wierzchołków nieparzystego stopnia w grafie prostym jest parzysta .
Dowód: Z lematu o u ciskach dłoni wiadomo, e
deg( v 1 ) + ... + deg( v k ) + deg( u 1 ) + ... + deg( u l ) = 2 m ,
gdzie v i jest wierzchołkiem o nieparzystym stopni, natomiast u i – parzystym.
Wiadomo, e suma liczb parzystych deg( u 1 ) + ... + deg( u l ) jest liczb parzyst ,
wi c suma deg( v 1 ) + ... + deg( v k ) ma równie parzyst warto , co jest
spełnione tylko wtedy, gdy ilo składników jest parzysta ( k jest parzyste) .
Def. Ci giem stopniowym grafu nazywamy uporz dkowany nierosn co
ci g stopni jego wierzchołków.
Def. Ci g stopniowy jest graficzny , gdy jest on ci giem stopni
pewnego grafu.
Tw. Havla Ci g stopniowy ( k , d 1 ,..., d l ) jest graficzny wtedy i tylko wtedy, gdy
po posortowaniu ci g ( d 1 – 1 ,d 2 – 1 ,..., d k – 1 ,d k +1 ,d k +2 ,..., d l ) jest graficzny .
5
Ci gi graficzne
Algorytm sprawdzaj cy, czy ci g stopni jest graficzny :
1. Je li d 1 = ... = d l = 0, to ci g jest graficzny
2. Je li d 1 < 0, to ci g nie jest graficzny
3. Uporz dkuj ci g nierosn co wg stopni
4. Usu z ci gu pierwsz (najwi ksz ) liczb d 1 i odejmij 1 od kolejnych
d 1 liczb ci gu
5. Wró do punktu 1
Przykład: Sprawdzi , czy podany ci g jest graficzny:
( 4, 3, 3, 2, 2 )
( 2, 2, 1, 1 )
( 1, 0, 1 )
( 1, 1, 0 )
( 0, 0 )
Odpowied : podany ci g stopniowy jest graficzny.
10572512.004.png
Zgłoś jeśli naruszono regulamin