0000016 2

Rys.2.3

2.2. Macierzowe przedstawienie grafów i hipergrofów

oprowadzimy najpierw pojęcia: incydencje i przyloglotć olomentów hiporgrafu i grefu.

oiorzchołok ytX Juct lncydentny z hiporga-łęzip uC U, o hlporgołpż u joot incydentna z wiorzchołkier y wtedy i tylko wtedy, gdy jest prawdziwe zdanie

V X-<Xj.....V.....*_r>

<X,U>€P

Wierzchołki y i z ep do siebie przyległe wtedy 1 tylko wtody, gdy

V ({x- <Xj...........X.....^xr>}v{*« <*!.....¹.....y.....*r>}]

<*.u>CP

Hipergałęzie u i v op do oiebie przyległa wtedy i tylko wtody, gdy iotnieje wierzchołek x€X incydontny jednocześnie z obu tymi hipergełpzlooi.

Olo hlpergrafu eymetrycznego, zwykłego lub nlezorlentowa -nego bez hlporpętli, zapieanego w poetecl H «<X, (Ej}> . definicje incydencji i przyległoAci możne zapieać w bardziej zwięzłej formie, wierzchołok xtX jeot incydentny z hlporkrawędzię Uj okreilonę podzbiorem Ej wtedy i tylko wtedy, gdy xfcEj.Wierzchołki x,y € x cq przyległe wtedy i tylko wtedy, gdy

V [*EEj A y_£Ej]

Hlpergałęzle E..E. eę przyległe wtedy i tylko wtedy, gdy Ej O E_k / J3 .

W odnieeieniu do grafu G • <X.U.P> , zepley formalne de -finicjl pojęć incydencji 1 przyległoAci oę neetępujęcet

Wierzchołek x₁ jeet Incydentny z gałęzlę Uj wtedy i tylko wtedy, gdy

v <y.x₁,Uj>e p]

Wiorzchołek x Jeet przyległy do wierzchołka y wtedy i tylko wtedy, gdy

V [<x.y,u> € P v <y,x,u>£ p]

ueu

Gałęzie u i v eę przyległe do eleble wtedy 1 tylko wtedy, gdy letnieje wierzchołek x€X Incydentny JodnoczeAme z gełęzię u i v.

2.2.1. Macierze incydencji

Grafy i hipergrafy możno przedetowlć za pomocę macierzy incydencji A - [•_lJ]„_ą|1 ; n - 1X1 z m - |U|.

Zależnie od potrzeby wykorzyetuje eię będż macierze dwu -wartoAclowe (binarne), będż wlelowartoAclowe, Wymagane Jeet przy tym ponumerowanie wierzchołków 1 gałęzi. Element a^ macierzy A ok.rcóla czy i w jaki opooób wierzchołek x. jeet Incydentny z ga-łęzię Uj.

31