Grafy.pdf

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.

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:

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 )} )

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.

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 .

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.

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: