0000026 2

clowy H* ■ <»X, u'. P'> Joot Jodnoznacznle określony podzbioroa hlporgołęzl u'.

Przykład 3.3

Wyznaczymy hlpcrgref częściowy H • <X, U, P> hlporgrafu H* »<X, U', P’> z przykładu 2.1, ekroślony podzbiorom hlporgołęzl U* ■ [b.d,g| .

Otrzymamy j

p' - P^u p'₂*j PljU P^ , gdzie P\ - {<3.2.b>}cP₁ ;

P‘₂ - l<,1.2.4.d>} CP₂ ;

P*₃ - {< l,2,5,4,g>} C P^ ;

P\ • 9

Grafom częściowym G¹ ■ < X*. U¹. P'> grafu G ■<X, U, P> Jest każdo toka część grafu G, dlo któroj X* • X. Graf częściowy Jest jednoznacznie określony podzbiorom gałęzi

u'c u.

Przykład 3.4

v/yznocżymy graf częściowy C* grafu G z rya.2.3, określony podzbiorem gałęzi U* ■ (n.l.pj.

Ot rzymoay:

Uzyskany graf częściowy joot przedstawiony no rys.3.2

Ryo.3.2

Podhłporgrtf częściowy h" hlporgro-fu H Joot to hiporgrof częściowy hiporgrofu H¹, który joot pod-hiporgrafon hiporgrofu H.

Podgrafoo częściowym c" grofu C Joot kożdy grof częściowy grafu G¹, który joot podgrafoo grofu G.

Nadgrefon (nodhiporgrofoo) grafu G (hiporgrofu H) nazywany kożdy grof (hiporgrof), którogo częś -cię Joot grof G (hiporgrof H).

Zwięzki między zdofiniowanyoi częściami grafów (hiporgro-fów) przodotowia eymbolicznle ryo.3.3.

Ryo.3.3

Z dofinlcji podgrofu    wynika, źo    dlo grofu G ■ <X,U,P>    ; |X| •

■ n, |u| ■ n, joot    2ⁿ różnych    podgrafów. Wśród    nich    Joot grof

zerowy (boz wiorzchołków), który moźorny oznaczyć    eymbolicznio

c° 9. 9 >.

Z definicji grofu częściowogo wynika, żo graf G ao 2^m różnych grafów częściowych. 'Wśród nich Joot grof puoty (bez gołęzi) C-<X. 9. 9> .

Powyżozo uwagi dotyczę równloż hiporgrafów, przy czy* hi-porgrof boz wiorzchołków (hiporgrof zerowy) Joot określony identycznie Jak graf zerowy, a hiporgrof puoty H • <X, 9, 9) Joot hiporgrofocn boz hiporgałęzi.