Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
30
2.Podstawowewłasnościgrafów
UsunięciekrawędzivewgrafuG=(V,E)dajewwynikugrafG
●
2.5.Elementarneoperacjenagrafach
–e=(V,E\{e}).Na
rysunku2.7ajestprzedstawionypewiengrafG,anarys.2.7bgrafG
–e,e={1,4}.
DodaniekrawędziełączącejwierzchołkivÎV,vÎVdajegrafG
+e=(V,EÈ{e}).
Narysunku2.7cjestpokazanygrafG
+ezrys.2.7azdodanąkrawędziąłączącąwierz-
chołki2i3.
Zwarciewierzchołkówv,ugrafudajewwynikugrafG
vu,wktórymwierzchołki
u,vsązastąpionenowymwierzchołkiem,oznaczonymv,w,incydentnymzkrawę-
dziamisąsiadującymizwierzchołkiemvlubwierzchołkiemuwG.Jeżeliwierzchołki
v,ubyłypołączonekrawędzią,topoichzwarciupowstajepętlawłasna.Przykład
grafuG
vuzezwartymiwierzchołkami1i2widaćnarys.2.7d.
UsunięciewierzchołkaG
–voznaczaV′=V\{v}orazE′=E\adj{v}dlagrafunie-
zorientowanegoiE′=E\{adj+(v)Èadj
-(v)}dlagrafuzorientowanego.GrafG
–vzusu-
niętymwierzchołkiemv=1jestpokazanynarys.2.7e.
Rys.2.7.Elementarneprzekształceniagrafów:a)graf;b)usu-
nięciekrawędzi;c)dodaniekrawędzi;d)zwarciewierzchoł-
ków;e)usunięciewierzchołka
Zadanie2.1
●
2.6.Zadania
Narysowaćgraf,któregowierzchołkamisą2-elementowepodzbiory4-elementowego
zbioruX={1,2,3,4},aparawierzchołkówuÎV,vÎVjestpołączonakrawędzią
niezorientowanąwtedyitylkowtedy,gdy½uÇv½=1.Czyjesttografregularny?
