Matematika | Középiskola » Lineáris algebra és gráfok

FEJEZET 6 Lineáris algebra és gráfok "És akkor hirtelen meglátta, hogy a mélyből megannyi bűnös követi őt a pókfonálon, és hogy rendületlenül másznak följebb és följebb, mint a megeredt hangyaboly." Akutagava Rjúnoszuke: A Vihar Kapujában, Európa Könyvkiadó Bp., 1974 29 o Az elmúlt XX. századot sok matematikus a lineáris algebra századának nevezte Jó néhány gráfelméleti kérdésről is bebizonyosodott, hogy hatékonyan kezelhető lineáris algebrai módszerekkel. Fordítva is működik a dolog Például nagyszámú áramköri elemet tartalmazó elektromos hálózatok tervezésekor adódik olyan feladat, amely több millió ismeretlent és egyenletet tartalmazó egyenletrendszer megoldását követeli meg. Az előbb említett egyenletrendszerek, hatékonyan oldhatók meg gráfelméleti eszközök felhasználásával. A digitális számítógépek, ill. a gépeken futó programok leírásánál gyakran használt eszköz a 2 elemű test

feletti n dimenziós vektortér A következő alfejezetben felidézzük az említett vektorterekkel kapcsolatos legalapvetőbb ismereteket. 1. Vektorterek a 2 elemű test felett 6.1 Definíció Legyen a V Abel-csoport F pedig test V -t F feletti vektortér nek mondjuk (jele: V (F )), ha adott az F × V V leképezés, amelyet skalárral való szorzásnak nevezünk, ha rendelkezik a következő tulajdonságokkal: 1. ∀v ∈ V : 1v = v, ahol 1 ∈ F 2. ∀α, β ∈ F és ∀v ∈ V : (α + β)v = αv + βv 3. ∀α ∈ F és ∀u, v ∈ V : α(u + v) = αu + αv 4. ∀α, β ∈ F és ∀v ∈ V : (αβ)v = α(βv) A 2 elemű test izomorf a Z2 -vel (a mod(2) maradékosztály gyűrűvel), melynek a Cayley-féle + 0 1 · 0 1 0 0 0 összeadási ill. szorzó táblája a következő: 0 0 1 1 1 0 1 0 1 Bármely A halmaz P (A) hatványhalmazát tekinthetjük Z2 feletti vektortérnek, mivel P (A) a szimmetrikus-differencia képzésére nézve Abel-csoportot alkot: def ∀X, Y ∈ P (A) : X

∆ Y = (X − Y ) ∪ (Y − X) Valóban: 1. ∀X, Y ∈ P (A) : X ∆ Y = (X − Y ) ∪ (Y − X) ∈ P (A), azaz a ∆ művelet kétváltozós algebrai művelet. 2. ∀X, Y, Z ∈ P (A) : (X ∆ Y ) ∆ Z = X ∆ (Y ∆ Z), azaz a ∆ művelet asszociatív 67 68 6. LINEÁRIS ALGEBRA ÉS GRÁFOK 3. ∀X ∈ P (A) : X ∆ ∅ = ∅ ∆ X = X, azaz a ∆ műveletre nézve az ∅ fog megfelelni a zéruselemnek. 4. ∀X ∈ P (A) : X ∆ X = ∅, azaz a ∆ műveletre nézve bármely részhalmaz önmaga inverze 5. ∀X, Y ∈ P (A) : X ∆ Y = Y ∆ X, azaz a ∆ művelet kommutatív P(A) elemeit karakterisztikus függvényeikkel reprezentáljuk, s a karakterisztikus függvényeket pedig rendezett elem n-esekkel adjuk meg. Az egyszerűség kedvéért legyen A = {1, 2, ., n}, s az X, Y ⊆ A (X, Y ∈ P (A)) részhalmazokat adjuk meg az X ↔ x = (x1 , x2 , ., xn ) ill az Y ↔( y = (y1 , y2 , ., yn ) hozzárendelésekkel, ahol a megfelelő komponensekre 1, ha i ∈ X xi = illetve

0, ha i ∈ /X ( 1, ha i ∈ Y yi = ahol 0, 1 ∈ Z2 . 0, ha i ∈ /Y Valóban, ez esetben X ∆ Y ↔ x + y = (x1 + y1 , x2 + y2 , ., xn + yn ), ahol az összeadást értelemszerűen Z2 -ben végezzük el, azaz 1+1=0 lesz például A skalárral való szorzás értelemszerűen oly módon történik, hogy ∀X ∈ P (A) : 1X = X illetve 0X = ∅, s az írás gyakorlása végett verifikálja a Tisztelt Olvasó, hogy a skalárral való szorzás 4 tulajdonsága teljesül. Az a1 , a2 , , ak−1 , ak vektorokat lineárisan függetlennek mondjuk, ha a 0 vektor az α1 a1 + α2 a2 + . + αk−1 ak−1 + αk ak alakban csak triviális módon áll elő, azaz csak akkor, ha α1 = α2 = . = αk−1 = αk = 0 Az a1 , a2 , , ak−1 , ak vektorok generálják a V (F ) vektorteret, k P ha bármely x vektora a V (F ) vektortérnek felírható x= αi ai alakban. Az a1 , a2 , , ak−1 , ak i=1 vektorok a V (F ) vektortérnek egy bázisát alkotják, ha egyrészt generálják V (F )-et, másrészt

lineárisan függetlenek. Az X ↔ x = (x1 , x2 , , xn ) megfeleltetés miatt nyilvánvaló, hogy P (A) n dimenziós vektortér Z2 felett. Lineáris algebrából ismert az a tétel, mely szerint bármely F test feletti n dimenziós vektortér izomorf az F test rendezett elem n-esei vektorterével. Ajánljuk a Kedves Olvasónak, hogy lássa be, hogy a 2 elemű test feletti Vn (Z2 ) vektortér bázisainak a száma (2n − 1)(2n − 21 )(2n − 22 ).(2n − 2n−2 )(2n − 2n−1 )-gyel egyenlő Felidézzük, hogy a V vektortér x, y vektorait ortogonálisnak (merőlegesnek) mondjuk, ha skaláris szorzatuk 0, azaz ha hx, yi = 0. S tudjuk azt is, hogy ortonormált bázisban a skaláris i=n P szorzat a hx, yi = xi yi = x1 y1 + x2 y2 + . + xn yn formulával számolható ki Értelemszerűen i=1 jelen esetben is mikor F = Z2 és V = P (A), X, Y ∈ P (A)-t ortogonálisnak (merőlegesnek) mondjuk, ha az X, Y részhalmazoknak megfeleltetett x, y rendezett elem n-esek skaláris szorzata 0-t ad

Z2 -ben. A Tisztelt Olvasó bizonyára felfigyelt arra, hogy a valós vektorterekben a 0 vektor az egyetlen, amely az összes többi vektorra és így önmagára is merőleges A 2 elemű test feletti vektorterek esetén azonban bármely olyan vektor merőleges lesz önmagára, amelynek páros sok koordinátája különbözik 0-tól. Például: ha a=(1, 1, 0), akkor a merőleges önmagára, mivel az önmagával vett skaláris szorzata ha, ai = 1 · 1 + 1 · 1 + 0 · 0 = 1 + 1 + 0 = 0. Ugyancsak megemlítenénk, hogy a Vn (F ) vektortér H1 , H2 altereit ortogonálisnak mondjuk, ha (x ∈ H1 és y ∈ H2 ) ⇒ hx, yi = 0. Továbbá a Vn (F ) vektortér H alterének ortogonális komplementere H c , ha egyrészt ortogonálisak, másrészt ∀z ∈ Vn (F ) : ∃x ∈ H és y ∈ H c , melyekre teljesül, hogy z = x + y. 6. VEKTORTEREK A 2 ELEMŰ TEST FELETT 69 T G 1. ábra Legyen most adott az egyszerűség kedvéért egy egyszerű összefüggő G = (E, ϕ, V ) gráf. A G=(E, ϕ, V

) gráfhoz az élei P (E) hatványhalmazához hozzárendelt vektortért rendeljük. Azaz a G = (E, ϕ, V ) gráf vektorterének elemei gráfunk éleinek tetszőleges részhalmazai E1 , E2 , s ezen részhalmazoknak mint vektoroknak az összege egyenlő e részhalmazok szimmetrikus differenciájával. Rögzítsük le a G=(E, ϕ, V ) gráfnak valamely T (ET ⊆ E, ϕT , VT =V ) feszítőfáját (Lásd az 1. ábrát!) Tudjuk, hogy T -nek bármely e éle hídja S az e él törlésével T kettő fa T1 (E1 , ϕ1 , V1 ), T2 (E2 , ϕ2 , V2 ) komponensre esik szét. Ez egyúttal azt is jelenti, hogy a G = (E, ϕ, V ) gráf csúcspontjai két nem üres részhalmazra bomlanak fel: V = V1 ∪ V2 . S G éleinek azt az E 0 részhalmazát, amely G-nek pontosan azon e0 éleit tartalmazza, amelyekre teljesül, hogy valamely v1 ∈ V1 csúcsot kötnek össze valamely v2 ∈ V2 csúcsponttal, G-nek a T feszítőfára vonatkozó e által generált alapvágatának mondjuk. A 2 ábrán a feszítőfa

kiválasztott élét vastag vonallal jelöltük és a V1 halmazt bekarikáztuk. A feszítőfa alá rajzoltuk az adott élhez tartozó vágás éleit ill. a G gráf csúcspontjait A G=(E, ϕ, V ) gráf T (ET , ϕT , VT ) feszítőfájára vonatkozó e ∈ E − ET éle által generált C alapkör e az az egyértelműen meghatározott C köre G-nek, amelyet akkor kapunk, amikor a T feszítőfa éleihez hozzávesszük e-t. A G gráf T feszítőfájára vonatkozó V alapvágatai által generált altért, a G gráf T feszítőfájára vonatkozó vágások HV alterének mondjuk. A G gráf T feszítőfájára vonatkozó C alapkörei által generált altért a G gráf T feszítőfájára vonatkozó körök HC alterének mondjuk. 6.1 Tétel A G = (E, ϕ, V ) gráf T (ET , ϕT , VT ) feszítőfájára vonatkozó vágások HV altere ortogonális a körök HC alterére. Bizonyítás: A bizonyítás egyrészt azon alapul, hogy a vágások alterének bármely eleme lineáris kombinációja az

alapvágásoknak, s a körök alterének bármely eleme lineáris kombinációja az alapköröknek. Másrészt bármely alapvágatnak és bármely alapkörnek páros sok közös éle van, ami jelen esetben azt jelenti, hogy bármely alapvágat merőleges (ortogonális) bármely alapkörre. S a Tisztelt Olvasó könnyen ellenőrizheti, hogy ha az A, B vektorhalmazokra teljesül, P P hogy ∀a ∈ A, ∀b ∈ B : ha, bi = 0, akkor az is fog teljesülni, hogy ha x = xi a i , y = yj bj és ∀xi , yj ∈ Z2 valamint ai ∈ A, bj ∈ B, akkor hx, yi = 0. Rövidebben úgy is mondhatnánk, hogy ha az A, B vektorhalmazok olyanok, hogy bármely A-ból való vektor merőleges bármely B-ből való vektorra, akkor az A ill. B vektorhalmazok által generált alterek HA , HB is merőlegesek egymásra. 70 6. LINEÁRIS ALGEBRA ÉS GRÁFOK 2. ábra G-nek T -re vonatkozó alapvágatai 6.2 Tétel A G = (E, ϕ, V ) gráf T (ET , ϕT , VT ) feszítőfájára vonatkozó vágások HV altere akkor és

csak akkor ortogonális komplementere a körök HC alterének, ha HV ∩ HC = {0} (0 ↔ ∅). 2. Mátrix reprezentációk "A vele teremtőt keresi a teremtő, azokat akik új értékeket új táblákra írnak." Nietzshe Frigyes: Ím-igyen szóla Zarathustra. Grill Károly Könyvkiadó vállalata, Bp. 1908 2.1 Az illeszkedési mátrix. 6. MÁTRIX REPREZENTÁCIÓK 71 3. ábra G-nek T -re vonatkozó alapkörei 6.2 Definíció A G = (E, ϕ, V ) irányítás nélküli gráf illeszkedési ill incidencia mátrix a An,m (ai,j ), ahol ai,j = 1, ha a vi csúcs illeszkedik az ej élre és 0 egyébként, ha az ej él hurokél, a j-edik oszlop minden eleme 0.  e1 e2 e3 e4 e5 e6 e7 e8 e9 e10 e11 0  v1  0 1 0 0 0 0 0 0 0 0   0  v2  0 1 1 0 0 0 1 0 0 0   0  v3  0 0 1 1 0 1 0 0 0 0   0  A = v4  0 0 0 1 1 0 0 0 0 0  0 0 0 0 1 1 1 0 0 0 0  v5    v6  0 1 0 0 0 0 0 0 0 0 1   v7  0 0 0 0 0 0 0 1 1 1 0  v8 0 0 0

0 0 0 0 0 1 1 1 e1 e9 v3 v1 v8 e1 e4 0 e2 e11 e8 v7 e5 e7 v6 v2 v5 v4  e3 e6 4. ábra 72 6. LINEÁRIS ALGEBRA ÉS GRÁFOK A továbbiakban az illeszkedési mátrixot olykor incidencia mátrixnak is mondjuk, de a két elnevezést teljesen azonos értelemben használjuk. A fenti definícióban a csúcsok számát n az élek számát m jelölte, azaz |V | = n és |E| = m. Hurokélekről nem ad használható információt a gráf illeszkedési mátrixa. Ha a G1 és a G2 gráfok izomorfak, akkor az illeszkedési mátrixaik A1 ill. A2 a soraik ill oszlopaik alkalmas permutálásával egymásba átvihetők Ha a mátrixok egyformák, akkor nem tudjuk, hogy a megfelelő gráfok izomorfak-e, mivel az illeszkedési mátrix nem ad felvilágosítást arról, hogy egy hurokél melyik csúcspontra illeszkedik és melyikre nem. A továbbiakban csak olyan irányítatlan gráfok illeszkedési mátrixairól beszélünk, melyeknek nincs hurokélük. A 4 ábrán levő mátrix a vele szomszédos

gráf illeszkedési mátrixa A mátrix 2 blokkból áll, mivel a gráfnak két komponense van, és először az első komponensbe tartozó csúcsokat ill. éleket adtuk meg Általában is igaz, ha valamely G gráf k komponensből áll, alkalmas módon indexelve a csúcsait és oszlopait az illeszkedési mátrixa k blokkból fog állni,   A1 0 . 0  0 A2 . 0  azaz a mátrix az alábbi alakú lesz A =  . .  , ahol az Ai a G gráf i-edik  . .  . 0 komponensének az illeszkedési mátrixa. 0 . Ak 6.3 Tétel Ha a G gráf rendje n és k komponensből áll és illeszkedési mátrixa A, akkor rg(A) = n − k, (a mátrixot a Z2 test fölöttinek tekintjük, azaz mod(2) számolunk). Bizonyítás: A bizonyítást a komponensek száma szerinti teljes indukcióval végezzük. Lényegében a tétel előtt említett blokk felbontás miatt elegendő az állítást k = 1 esetén belátni, mivel a "főátlón" kívül mindenütt 0 áll és emiatt a blokkokból

álló hipermátrix rangja megegyezik a főátlóban álló blokkok rangjainak összegével. Legyen G1 első komponense G-nek és legyen csúcsainak száma n1 , s illeszkedési mátrixa A1 . Az A1 mátrix rangja legfeljebb n1 − 1 lehet. Valóban, adjuk az A1 mátrix minden sorát az A1 mátrix utolsó sorához Ekkor az utolsó sor minden eleme 0 lesz, mivel minden oszlopban 2 darab egyes van (egy él pontosan két csúcsra illeszkedik). Ha n1 -nél kevesebb s1 sor összege is 0-t adna, például az i1 , i2 , , is1 , akkor a v1 , v2 , ., vs1 csúcsok egyikéből sem vezetne él valamely másik a v1 , v2 , , vs1 pontoktól különböző csúcspontba, ellentmondva annak, hogy G1 összefüggő volt. Az előbb mondottak megismételhetők G bármely komponensére vonatkozólag, s figyelembe véve, hogy a speciális alakú A hipermátrixunk Ai blokkjainak rangjainak az összege magának a hipermátrixnak a rangjával egyezik meg, az állítást bebizonyítottuk. ¤ Ha a G gráf A

illeszkedési mátrixából komponensenként egy-egy sort elhagyunk, akkor G ún. redukált incidencia mátrix át kapjuk Nem nehéz belátni, hogy ha valamely kvadratikus (n − k) · (n − k)-as részmátrix determinánsa nem 0 ,akkor a részmátrix oszlopaihoz tartozó élek G minden komponensének kijelölik egy-egy feszítőfáját. 6.4 Tétel Ha a G gráf e1 , e2 , , ek élei kört alkotnak, akkor az incidencia mátrix (a redukált incidencia mátrix) e1 , e2 , ., ek által kijelölt oszlopai lineárisan függők Bizonyítás: A kijelölt oszlopoknak megfelelő élek közül kettő vagy 0 illeszkedik bármely csúcspontra, ezért a kijelölt oszlopok bármely sorában 2 vagy 0 darab 1-es áll, s ezek összege mod(2) valóban 0. Azaz a szóban forgó vektorok összege 0, s ez pontosan azt jelenti, hogy függők ¤ 6. MÁTRIX REPREZENTÁCIÓK 73 6.3 Definíció A G = (E, ϕ, V ) irányított gráf illeszkedési mátrix ának nevezem az An,m (ai,j ) mátrixot, ahol ai,j = 1,

ha a vi csúcsba fut be az ej él, ai,j = −1, ha a vi csúcsból fut ki az ej él és 0 egyébként. Ha az ej él hurokél, a j-edik oszlop minden eleme 0 Irányított gráf incidencia mátrixára is hasonló állítások igazolhatók, mint amilyeneket az irányítás nélküli gráfokra igazoltunk, de H. Poincare alábbi tétele rávilágít bizonyos eltérésekre 6.5 Tétel Ha az A kvadratikus mátrix valamely G gráf incidencia mátrixának nem nulla determinánsú részmátrixa, akkor |det(A)| = 1. Bizonyítás: Természetesen itt a valós számtest fölött számoltuk a determinánst. Legalább egy oszlop van a szóban forgó determinánsban, amelyben csak egy elem különbözik 0-tól. Fejtsük ki e sor szerint, és az eggyel alacsonyabb rendű aldeterminánsra ismételjük meg az előbbi okoskodást. Ezt az eljárást megismételve annyiszor, mint amennyi a determináns rendje, végezetül a bizonyítandó állítás adódik. ¤ A G=(E, ϕ, V ) irányított gráf incidencia

mátrixának a redukált incidencia mátrixát ugyanúgy értelmezzük, mint az irányítatlan esetben, azzal a különbséggel, hogy itt a valós test felettinek tekintjük a mátrixot. Értelemszerűen az oszlop illetve sorvektoraival is oly módon számolunk mint, amelyek az R valós test feletti oszlopvektorok ill sorvektorok teréből valók Vegye észre a Kedves Olvasó, hogy ha az A illeszkedési mátrix valamely i-edik sorához hozzáadjuk az összes többi j-edik sorait, akkor az i-edik sor minden eleme 0 lesz, mivel minden oszlopban vagy csupa 0 áll (ha az illető oszlopnak megfelelő él hurokél), vagy pontosan egy darab +1 és egy darab -1 és az összes többi elem 0-val egyenlő. Ez egyrészt pontosan azt jelenteni, hogy az n csúcspontú gráf incidencia mátrixának a rangja legfeljebb n − 1 lehet, másrészt szabad kezünk van abban, hogy az n csúcspontú gráf illeszkedési (incidencia) mátrixának melyik csúcspontjának megfelelő sorát töröljük, hogy

megkapjuk a redukált incidencia mátrixát. A következő tétel bizonyításánál pontosan e szabad választás lehetőségével operálunk. 6.6 Tétel Legyen a G=(E, ϕ, V ) irányított gráfnak részgráfja a T (E 0 , ϕ0 , V 0 ) fagráf, akkor a T részfa AT redukált incidencia mátrixának determinánsa vagy +1-gyel vagy -1-gyel egyenlő, azaz det(AT ) = ±1. Bizonyítás: A T fa gráf csúcspontjainak a száma n (2 ≤ n) szerinti teljes indukcióval bizonyítunk. Az n = 2 esetben az AT redukált incidencia mátrix 1x1-es és determinánsa valóban vagy +1, vagy -1. Tegyük fel, hogy az állításunk igaz bármely n csúcspontú T 0 részfára és bizonyítsuk az n + 1 csúcspontú T részfára Tudjuk, hogy bármely fagráfnak van legalább 2 elsőfokú csúcspontja. Tegyük fel, hogy a T fa gráfunknak u és v elsőfokú csúcspontjai Tegyük fel, hogy a T fagráf AT redukált incidencia mátrixát az u csúcsnak megfelelő sor törlésével kaptuk. Fejtsük ki AT -t a v

csúcsnak megfelelő i-edik sor szerint, a v választása miatt az i-edik sorban csak egy elem mondjuk ai,j 6= 0, s annak az értéke ai,j = ±1, mivel csak egy él illeszkedik v-re, mondjuk a j-edik. Az i-edik sora szerint kifejtve a det(AT )-t ai,j (−1)i+j det(AT 0 )-t kapjuk, ahol az AT 0 annak a T 0 részfának a redukált incidencia mátrixát jelöli, amelyet T -ből a v csúcs törlésével kaptunk és a T 0 részfának már pontosan n csúcspontja volt, azaz T 0 -re már teljesült az indukciós feltevés, ezért det(AT 0 ) = ±1, amiből már valóban adódik, hogy det(AT ) = ±1. S ezzel a bizonyítás kész. ¤ 74 6. LINEÁRIS ALGEBRA ÉS GRÁFOK Jelölje p az n csúcspontú G = (E, ϕ, V ) irányított gráf komponenseinek a számát, ekkor a 6.3 tételből egyszerűen következik, hogy a G = (E, ϕ, V ) irányított gráf redukált incidencia mátrixának rangja n − p. 2.2 A körmátrix A K(ki,j ) körmátrix azt mutatja, hogy a G=(E, ϕ, V ) gráf élei mely

körökben szerepelnek. Lényegében a körmátrix megadása előtt felsoroljuk a G=(E, ϕ, V ) gráf összes körét és az i-edik körnek megfeleltetjük az i-edik sort és az i-edik sor j-edik oszlopába 1-et írunk, ha a j-edik él illeszkedik az i-edik körre, különben 0-t írunk. 6.4(Definíció A G=(E, ϕ, V ) irányítatlan gráf körmátrix a K(ki,j ), ha 1, ha ej éle a ki körnek ki,j = 0, ha ej nem éle a ki körnek Irányított G gráfhoz, ha minden körhöz már kijelöltünk egy-egy bejárási irányt, akkor az alábbi utasítással rendelünk körmátrixot:    1, ha ej éle a ki körnek és irányuk egyező ki,j = −1, ha ej éle a ki körnek és irányuk különböző   0, ha e nem éle a k körnek j i Felírjuk az alábbi irányított (irányítatlan) gráf K1 , (K2 ) körmátrixát. Folytonos vonallal rajzoltuk a G gráf F feszítőfájának (favázának) éleit. v5 v1 e3 e6 e1 v3 e2 e8 e7 e9 v4 e5 e4 v2 5. ábra A körök ill. élek

sorrendjét az alábbi szabály szerint adjuk meg Kijelöljük a G gráf egy F favázát (ha G nem volt összefüggő, akkor minden egyes komponensének megadjuk egy favázát). Először az F fára vonatkozó ei kötőéleket indexeljük (itt i-vel) és az általuk meghatározott köröket ki -vel. Itt jegyezzük meg, hogy a G gráf F favázára vonatkozóan az e él kötőél, ha nem éle F -nek. A G gráf F feszítőfája és e kötőéle egyértelműen meghatározza G-nek egy k körét, mivel F maximális összefüggő kört nem tartalmazó részgráfja volt G-nek. Irányított gráfok előbb említett alapköreit F -re vonatkozó kötőéleinek megfelelően irányítjuk. 6. MÁTRIX REPREZENTÁCIÓK 75    1 0 0 0 0 1 −1 0 0 1 0 0 0 0 1 1 0 0  0 1 0 0 0 1 1 0 0   0 1 0 0 0 −1 1 0 0       0  0 0 1 0 0 1 0 1 0  0 1 0 0 1 0 1 0       0  0 0 0 1 0 0 1 1 0  0 0 1 0 0 1 1 0      0 0 0 1 0 0 0 0 

 0  0 0 0 0 1 0 0 0 0      1 0 0 1 0 0 0 0   1  1 1 0 0 1 0 0 0 0      K1 =  1 0 1 0 0 0 1 1 0  K2 =  −1 0 1 0 0 0 1 1 0      0 0 1 0 1 0 1 0   1  1 0 0 1 0 1 0 1 0   0  0 1 1 0 0 0 1 1 0  1 1 0 0 0 1 1 0       0 −1 0  0 1 0 1 0 1 0 1 0   1 1 0 0 1 0      0  0 0 1 1 0 1 1 0 0   1 −1 0 1 −1 0 0 0      1 0 1 1 0 0 0 0 0   1 0 −1 1 0 0 0 0 0  0 1 1 1 0 0 0 0 0 0 1 1 −1 0 0 0 0 0 0 Írjuk fel akorábban lerajzolt G ill. G irányított   gráf illeszkedési A1 , ill. A2 mátrixát is −1 1 −1 0 0 1 0 0 0 1 1 1 0 0 1 0 0 0  1 −1 0 −1 0 0  1 1 0 1 0 0 1 0 0  1 0 0        0 0 0 0 −1 −1 1 0  A1 =    0 0 0 0 0 1 1 1 0  A2 =  0  0  0 0 1 1 0 0 0 1 1  0 1 1 0 0 0 −1 1  0 0 0 0 0 0 0 0 −1 0 0 0 0 0 0 0 0 1 T T Vegyük észre, hogy AK =

N5,13 zérusmátrix és AB = N13,5 is.  6.7 Tétel Ha a G gráfnak az A illeszkedési illetve K körmátrixának oszlopai ugyanazon élsorozat szerint rendezettek, akkor AK T = N1 és KAT = N2 (mod 2) (itt N1 és N2 is zérusmátrixot jelöl). Bizonyítás: Az irányítás nélküli esetet tárgyaljuk és ott is csak az első állítást, mivel abból a második transzponálással megkapható. Ha az A ai sorához tartozó vi csúcs nem illeszkedik a kj körre, akkor a szorzatmátrix nij eleme 0, mivel a vi -re illeszkedő élek nem élei a kj körnek. Ha az A ai sorához tartozó vi csúcs illeszkedik a kj körre, akkor a szorzatmátrix nij eleme 0, mivel a vi -re illeszkedő élek közül pontosan 2 éle a kj körnek. ¤ 2.3 A csúcsmátrix Irányított és irányítás nélküli gráfok esetén egyformán definiálhatjuk a csúcs- (vagy szomszédossági) mátrix ot A mátrix aij eleme azoknak az éleknek a számával egyezik meg, amelyek vi -ből futnak vj -be, természetesen ha

az e él irányítás nélküli és ϕ(e) = (vi , vj ) = (vj , vi ), akkor úgy tekintjük, hogy e vi -ből megy vj -be és fordítva is, azaz e vj -ből megy vi -be. Azaz n csúcspontú irányítás nélküli G gráf csúcsmátrixa szimmetrikus n × n-es kvadratikus mátrix. Ha adott a G = (E, ϕ, V ) gráf, és |V | = n, akkor csúcsmátrixa n × n-es valós elemű mátrix. P 1. 6.5 Definíció A G=(E, ϕ, V ) gráfnak Vn×n = (ai,j ) csúcsmátrixa, ha ai,j = ϕ(e)=(vi ,vj ) Példa: Írjuk fel a 6. ábrán látható irányított gráf szomszédossági (vagy adjecencia mátrixát) Érdemes megjegyezni, hogy a csúcsmátrix a hurokélekről is informál. Továbbá, ha a G gráf csúcsait „A” módon indexelve csúcs mátrixa VA ill. „B” módon indexelve VB , akkor a sorok és az oszlopok alkalmas cseréjével elérhető, hogy az egyik mátrixot átvisszük a másikba. 76 6. LINEÁRIS ALGEBRA ÉS GRÁFOK v3 v1 v4 v5 v8 v6 v2  v1 0 v2  1 v7  v3  0  v4

 0 V =  v5  0 v6  0 v7  0 v8 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0  0 0  0  0  0 1  2 0 6. ábra Mivel ugyanazokat a sorokat és oszlopokat kell felcserélni, ezért van olyan P permutáció mátrix, melyre VA = P −1 VB P . A fentiekben lényegében beláttuk a következő tételt 6.8 Tétel Ha a G1 gráfnak a csúcsmátrixa A, és a G2 gráfnak csúcsmátrixa B, akkor a G1 és a G2 gráfok izomorfiájának szükséges és elégséges feltétele az, hogy létezzék olyan P permutáció mátrix, melyre teljesül, hogy A = P −1 BP . A csúcsmátrix hatványairól nem nehéz belátni az alábbi tételt. n 6.9 Tétel Legyen a G gráf csúcsmátrixa VA (VA )n -nek vi,j eleme megadja G vi és vj csúcsát összekötő irányított élsorozatoknak a számát. Bizonyítás: Teljes indukcióval bizonyítunk. n = 1 esetén az állítás adódik a csúcsmátrix (m)

definiciójából. Tegyük fel, hogy n = m-re igaz az állítás és igazoljuk (m + 1)-re Jelölje vi,k az indukciós feltevés szerint azon m hosszúságú irányított élsorozatok számát, melyek az i-edik (1) csúcsot a k-adik csúccsal kötik össze. Továbbá jelölje vk,j a k-adik csúcsot a j-edik csúccsal (m) (1) összekötő élek számát. A vi,k · vk,j szorzat megadja az i-edik csúcsból a j-edik csúcsba vezető olyan irányított m + 1 hosszúságú élsorozatok számát, melyek a k-adik pontra illeszkednek (m) (1) (mikor is k j-nek szomszédja). k szerint összegezve a vi,k ·vk,j szorzatokat, megkapjuk az i-edik k=n P (m) (1) (m+1) vi,k ·vk,j , csúcsból a j-edik csúcsba vezető irányított élsorozatok számát, másrészről vi,j = ami nem más, mint a csúcsmátrix (m + 1)-edik hatványának i, j-edik eleme. ¤ k=1 Megjegyzés. Ha valamely n természetes számra teljesül, hogy (VA )n = 0, akkor a gráf nem tartalmazhat irányított kört. Megjegyzés. A

csúcsmátrix jól alkalmazható valamely A halmazon adott, ρ bináris reláció tulajdonságainak a jellemzésére. A Gρ (E, ϕ, V ) gráfot a következő módon rendeljük az A halmazon adott ρ binér relációhoz: (i) G csúcspontjai A elemei lesznek, azaz A = V , (ii) (e = (vi , vj ) ∈ E ⊆ (A ⊗ A)) ⇔ (vi ρvj ), más szóval vi -t vj -vel akkor és csak akkor köti él össze, ha vi ρ relációban áll vj -vel. A ρ binér reláció akkor és csak akkor reflexív, ha a 6. MATROIDOK 77 Gρ (E, ϕ, V ) gráf VA csúcsmátrixának főátlójában mindenütt 1 áll. A ρ binér reláció akkor és csak akkor szimmetrikus, ha Gρ (E, ϕ, V ) gráf VA csúcsmátrixa szimmetrikus. 3. Matroidok "Vezér! A nagy császár karmos hada mi vagyunk. Minket kínzol, minket nyomorgatsz? Álltunkban sem pihenünk, csak talpalunk." 185. vers, Si King Dalok könyve, Európa Könyvkiadó, Bp. 1972 A matroidelméletet Hassler Whitney alapozta meg a lineáris függőség

algebrai elméletét vizsgáló 1935-ös dolgozatával. Az elmúlt 62 esztendőben több könyv is megjelent e tárgykörben A matroidelmélet sok alkalmazásra talált az áramkörök analízisében, kapcsoláselméletben, lineáris programozásban, hálóelméletben és gráfelméletben. 6.6 Definíció Az M = (E, I) rendezett párt matroid nak nevezzük, ha E véges halmaz és I részhalmaza E hatványhalmazának P (E)-nek. Továbbá I rendelkezik a következő tulajdonságokkal: (1) ∅ ∈ I, azaz az üres halmaz eleme I-nek (2) ha x ∈ I és y ⊆ x, akkor y ∈ I-nek, azaz I bármely x elemének bármely részhalmaza ismét eleme I-nek (3) ha Ip , Ip+1 ∈ I -nek és |Ip | + 1 = |Ip+1 |, akkor ∃x ∈ Ip+1 olyan, hogy Ip ∪ {x} ∈ I. Példák: (i) Legyen G=(E, ϕ, V ) egy egyszerű gráf és I jelölje G éleinek olyan részhalmazait, amelyek G-nek körmentes részgráfjait jelölik ki, ekkor az (E, I) pár rendelkezni fog a matroidoktól megkövetelt tulajdonságokkal. (ii)

Legyen E az M mátrix oszlopvektorainak a halmaza azaz E = {m1 , m2 , m3 , ., mj , , ms }, E lineárisan független oszlopvektorainak a halmazát jelöljük I -vel, ekkor az (E, I) pár matroidot alkot. Azokat az M = (E, I) matroidokat, amelyeknél E tekinthető valamely G gráf élei halmazának és I elemei a G körmentes részgráfjai élei halmazának, grafikus matroid oknak mondjuk. Azokat az M = (E, I) matroidokat, amelyeknél E tekinthető valamely mátrix oszlopvektorai halmazának és I a független oszlopvektorok halmazának a halmazaként, mátrixmatroid nak mondjuk. A matroidelmélet sok elnevezést, fogalmat vett át a lineáris algebrából ill. a gráfelméletből Kedves Olvasónknak ezekből nyújtunk át egy csokorra valót. Kicsit ömlesztve mellőzve ez egyszer a formákat, reméljük ez nem vezet félreértésre. Az I elemeit független halmaz oknak nevezzük. Az I halmaz B elemét bázisnak nevezzük, ha maximálisan független Itt a maximális jelző nyilván

abban az értelemben értendő, hogy E bármelyik olyan A részhalmazát is vegyük, amelyik valódi módon tartalmazza B-t (B ⊂ A), akkor az A nem eleme I-nek. Az E tetszőleges A részhalmazának a rangján r(A)-n az A maximálisan független részhalmazának az elemeinek a számát értjük. Ha E valamely A részhalmaza nem eleme I -nek, akkor azt függőnek mondjuk Az A (A ⊆ E) részhalmaz lezártján (vagy az A által feszített halmazon) azt az sp(A) halmazt 78 6. LINEÁRIS ALGEBRA ÉS GRÁFOK értjük, melynek rangja megegyezik A rangjával és maximális. Maximális abban az értelemben, hogy nem létezik olyan sp(A)0 halmaz, melynek a rangja ugyancsak megegyezne A rangjával és valódi módon tartalmazná sp(A)-t. Egy minimálisan függő K halmazt kör nek nevezzünk. Minimálisan függő nyilván abban az értelemben, hogy K-nak semelyik valódi részhalmaza sem lesz függő, azaz K bármely valódi részhalmaza már eleme I -nek, de maga K nem eleme I -nek. 6.10

Tétel Legyenek X, Y független részhalmazok M -ben Ha X elemeinek a száma kevesebb, mint Y elemeinek a száma, azaz |X| < |Y |, akkor létezik olyan Z ⊆ Y − X, hogy |X ∪ Z| = |Y | és X ∪ Z független M -ben. Bizonyítás: Legyen Z0 olyan, hogy rendelkezzék az alábbi tulajdonságokkal: (i) Z0 ⊆ Y − X (ii) X ∪ Z0 független M -ben (iii) Ha X ∪ Z független M -ben és Z ⊆ Y − X, akkor |X ∪ Z0 | ≥ |X ∪ Z|. Tegyük fel, hogy létezik olyan Z0 , hogy |X ∪ Z0 | < |Y |. Ekkor létezik egy olyan Y0 ⊆ Y , melyre |Y0 | = |X ∪ Z0 | + 1. Mivel Y0 független, lehet alkalmazni a matroidok 3 axiómáját Létezik y ∈ Y0 − (X ∪ Z0 ) olyan, hogy X ∪ Z0 ∪ {y} független M -ben, de a Z0 ∪ {y} létezése ellentmond (iii)-nek. Ezért |X ∪ Z0 | ≥ |Y |, s ezzel a bizonyítás kész ¤ 3.1 Következmény Az M matroid bármely B bázisának az elemszáma megegyezik M rangjával. Bizonyítás: Legyen |B1 | < |B2 |, akkor az előző tétel szerint

létezik olyan Z ⊆ B2 − B1 olyan, hogy Z ∪ B1 független, ami viszont ellentmond B1 maximalitásának. ¤ 3.2 Következmény Ha B1 és B2 bázisai M -nek és x ∈ B1 − B2 , akkor létezik olyan y ∈ B2 − B1 , melyre teljesül, hogy (B1 ∪ {y}) − {x} bázisa M -nek. Bizonyítás nélkül megemlítjük itt néhány tulajdonságát a rang függvénynek. 6.11 Tétel Legyen adott az M = (E, I) matroid és A, B ⊆ E és x ∈ E, ekkor: (1) 0 ≤ r(A) ≤ |A| (2) Ha A ⊆ B, akkor r(A) ≤ r(B) (3) r(A) ≤ r(A ∪ {x}) ≤ r(A) + 1 (4) Részmoduláris egyenlőtlenség: r(A) + r(B) ≥ r(A ∪ B) + r(A ∩ B) (5) Ha r(A ∪ {x}) = r(A ∪ {y}) = r(A), akkor r(A ∪ {x} ∪ {y}) = r(A). Ha az E n elemű halmaz legfeljebb k (0 ≤ k ≤ n) elemű részhalmazainak a halmazát választjuk I-nek, akkor egy M matroidot kapunk, melyet uniform matroid nak szokás nevezni. Jele: Un,k . Az Un,n matroidot szabad matroid nak mondjuk, mivel E bármely részhalmaza független, az Un,0

matroidot triviális matroid nak nevezzük, mivel csak az üres halmaz ∅ független benne. Nem nehéz belátni, U4,2 nem lehet grafikus matroid, mivel nincs olyan 4 élű gráf, hogy bármely 3 éle kört alkosson. A körökkel kapcsolatos következő állítások közvetlenül a definíció következményei. 6. MATROIDOK 79 6.12 Tétel (1) Bármely kör bármely valódi részhalmaza független. Ha C1 és C2 különböző körök, akkor C1 6⊂ C2 . (2) Ha C kör, akkor r(C) = |C| − 1. (3) Az M matroidban akkor és csak akkor nincs kör, ha E minden részhalmaza független, ekkor M -nek csak egy bázisa van ti. maga E 6.7 Definíció Az M (E, I) matroid duálisa az M ∗ (E, I ∗ ) pár, ahol I ∗ = {X ⊆ E : van olyan B bázisa M -nek, melyre X ∩ B = ∅}. Megjegyezzük, hogy M ∗ bázisa B ∗ = {E−B, ahol B bázisa M -nek}. M ∗ köreit vágásoknak is szokták nevezni M -ben vagy kokör öknek is mondják. 3.1 A mohóalgoritmus matroidokra Legyen adott az M (E,

I) matroid Bármely X ∈ I halmazra legyen értelmezve ext(X) = {y ∈ E − X : X ∪ {y} ∈ I}. Másszóval ext(X) az E halmaz azon y elemeinek az összeségét jelöli, amelyeket anélkül hozzá lehet venni az X halmazhoz, hogy függő halmazt kapnánk. Legyen megadva az E halmazon egy nem negatív w(x) súlyfüggvény, azaz legyen adott E-nek egy leképezése a nem negatív valós számok w halmazába: E − R+ ∪ {0}. Értelmezzük továbbá bármely X ⊆ E halmazra is w(X)-et a P w(x). A B bázist maximális súlyúnak (optimális bázisnak) következő formulával: w(X) = x∈X mondjuk, ha bármely más B 0 bázis esetén w(B) ≥ w(B 0 ). A következő algoritmus a mohóalgoritmus matroidokra: w Bemenet: az M (E, I) matroid és az E − R+ ∪ {0} súlyfüggvény. Kimenet: egy optimális B bázisa M -nek. Az algoritmus: 1. Legyen B = ∅ 2. Ha ext(B) = ∅, ugrás 5-re 3. Válasszunk egy olyan x ∈ ext(B) elemet, amelyre teljesül, hogy w(x) = max w(y) y∈ext(B) 4.

Legyen B = B ∪ {x} és ugrás 2-re 5. Visszatérés B-vel 6.13 Tétel A matroidok mohó algoritmusa mindig talál egy optimális bázist