ciklusban tér - studopediya
Hurkok - egy nagyon fontos része a szerkezet a grafikon, velük kell foglalkozni a sok probléma. Oszlop lehet sok cikluson keresztül (lásd. Feladat 5.15), ezért hasznos, ha egy eszközt egy kompakt leírása a készlet minden ciklusban a grafikonon, és manipulálni. Az egyik kényelmes eszköz az ilyen típusú készülék rendelkezik lineáris algebra.
Ezután vesszük grafikonok rögzített csúcsok halmaza V betű O fogja jelölni az üres gráf :.
Az összeg modulo 2 (a továbbiakban ebben a részben fogjuk nevezni egyszerűen az összeg), a két grafikon és egy grafikon ami a szimmetrikus különbség készletek.
A következő tulajdonságok lépett működés nyilvánvaló, vagy könnyen ellenőrizhető legyen.
1) kommutatív: minden, és.
2) Asszociativitás: minden.
3) minden egyes G.
4) bármely G.
Ez azt jelenti, hogy a grafikonokat a csúcsok halmaza V képez Abel-csoport alatt adagolási művelet modulo 2. Semleges elem ( „nulla”), ez a csoport egy olyan grafikon, O. ellentétes minden grafikon a grafikon magát. Egyenlet ismeretlen X és egy adott gráf G és H-nak egy egyedi megoldást. Mivel a tulajdonsága asszociatív tudjuk alkotnak egyfajta kifejezése nélkül zárójelek jelzik műveletek sorrendjét. Ez könnyen belátható, hogy a szélén tartozik grafikon akkor és csak akkor tartozik a páratlan számú grafikonok.
Tekintsünk egy sor két elemet. Ez az a terület, viszonyítva a műveletek a szorzás és modulo 2 szorzás elemek működését határozzák meg ezen a területen oszlopok: bármely gráf A grafikonokat a csúcsok halmaza V bemeneti műveletek az összeadás és szorzás a grafikon elemeinek a mező egy lineáris vektor teret (azaz . e. e tereket, engedelmeskedik az axiómák).
Fix egy grafikont, és megvizsgálja a készlet minden átívelő részgráfok. Ez a készlet tartalmaz elemeket, köztük magam G gráf és a grafikon. Ez zárt az összeadás és szorzás grafikon elemei a területen, tehát, egy altér az összes grafikonok. Ezt nevezik a helyet részgráfok G.
A részgráfok tér lehet egy természetes módja annak, hogy adja meg a koordinátákat. Felsoroljuk a széleit a G gráf .. Most spanning részgráf társítható jellemző vektor a beállított élek:
Kapunk egy-egy levelezés a készlet részgráfok és több dimenziós bináris vektorok. Az összeg a grafikonok megfelel vektorba (koordináta-bölcs) összege modulo 2 azok jellemző vektorok.
A többi ebben a szakaszban a „ciklus” Belátható egy kicsit másképp, mint korábban por.Imenno Count ciklus G budemnazyvat annak spanning részgráfot, amely egy csatlakoztatott komponens egy egyszerű ciklus, és a többi - izolált csúcsokat. Felöleli részgráf, melynek fok minden csúcsot is nevezett quasicycles. Ily módon minden egyes ciklus quasicycles és G jelentése - quasicycles.
Tétel a kvazitsiklah.Mnozhestvo összes quasicycles adott gráf zárt az összeadásra modulo 2.
Ez a tétel azt jelenti, hogy a készlet minden quasicycles gráf altér részgráfok, ez az úgynevezett tér ciklusok a grafikon.
Kompakt ábrázolása egy lineáris vektortér ad neki egy alapot. Alapján ciklusok helyet a továbbiakban egyszerűen alapjául ciklus. meg lehet építeni egy alapot a ciklusok a következők szerint. Mi választjuk ki a G minden frame T. Legyen - minden szélei gráf nem tartoznak a T. Ha ehhez hozzátesszük, hogy a T borda, akkor egy ciklus a kapott gráf. Így kapunk egy család s ciklus, ezek az úgynevezett alapvető ciklus vázhoz képest T.
A tétel az alapvető tsiklah.Mnozhestvo valamennyi alapvető ciklusok tekintetében semmilyen keret T egy gráf alapján ciklusok a tér a grafikon.
Ebből következik, hogy a tétel dimenzió a tér ciklusok egyenlő az élek száma a grafikonon, ez kívül van a keretben. Mivel a keret éleket tartalmaz, ahol k - száma a csatlakoztatott komponensek a grafikon, ez a méret megegyezik. Ez a szám az úgynevezett cyclomatic száma a grafikonon.
Frame Count meg lehet építeni egy csomó szempontból. A konstrukció a bázis ciklusok a grafikon különösen hasznos hosszában keresés át a fő tulajdonsága a DFS-fa - mindegyik átellenes szélén képest a fa hosszirányú. Ez azt jelenti, hogy a két csúcsa a szélén az őse a másikat a DFS-fa. Mindegyik borda folyamatban keresésének mélységet, hogy megfeleljen kétszer - egyszer, amikor az aktív node lesz az őse a másik alkalommal lesz leszármazottja. Ebben az utóbbi esetben, a kívánt alapvető ciklus a figyelembe vett bordát és egy visszirányú rész DFS-fán ezeket összekötő két csúcsot. De ez így van valahogy tárolni bypass alapos, mivel szükség van a későbbi visszatérés. Ha, például, tárolására nyitott csúcsok verem használunk, a csúcs az ezen az úton vannak a tetején a verem. Mindenesetre, ez az út könnyen elérhető, és a ciklus egyszerű.
Bár a mélységi keresést hajt végre a lineáris a csúcsok száma és élek az idő, döntő befolyást a bonyolultsága az algoritmus megtalálta kell megjegyeznünk, hogy ciklusokat. Kiszámítjuk a teljes hossza alapvető ciklusok kapott mélységi keresést a teljes gráf n csúcsú. DFS-fa ebben az esetben egy egyszerű módja, akkor viszonylag ciklus hossza 3, az a ciklus hosszát 4, ..., egy ciklus n hosszúságú. A hosszának összegét valamennyi alapvető ciklusok egyenlő lesz
Így egyes oszlopok számát ennek algoritmus rend műveletek értékét.
A ciklus tér szorosan kapcsolódik a helyet a grafikon darabok. Let. Bemetszés gráf A. meghatározott területén - egy feszítő részgráf, amelynek élei minden gráf élei csúcsokat összekötő A-tól csúcsot.
Tétel a razrezah.Mnozhestvo minden szakasz a grafikon zárt az összeadásra modulo 2.
Bemetszés meghatározott Singleton Egy úgynevezett elemi. Alapján a tér szakaszai összefüggő gráf nyerhető figyelembe valamennyi elemi részek, kivéve egy (bármilyen). Szétkapcsolt gráf egy kell tennie az egyes összefüggő komponens. Így a dimenzió a grafikon csökkenti a teret k komponensek egyenlő.
Hagyja, - a két jellemző vektorok átívelő részgráfok G. Azt mondják, hogy ezek al-oszlopok merőleges. if. Ez megegyezik a páros számú részgráfok közös élek.
Tétel ciklusok és ciklus razrezah.Lyuboy ez a grafikon azt merőleges bármilyen sorrendben.
Mivel az összeg a méretei a terek ciklusok és a vágások egyenlő a dimenzió a tér részgráfok, ebből az is következik, hogy a tétel ciklus tér és vágások ortogonális kiegészítik egymást. Ezt fel lehet használni, hogy össze egy alapot előfordulásának mátrix ciklusok. Nézzük ennek igazolására egy példát. Tegyük fel, hogy meg akarja találni alapot a ciklusok az ábrán látható grafikonon 8. Mi kivitelezést
előfordulási mátrix, és távolítsa el belőle az egyik (bármelyik) egy vonal (abban az esetben, egy leválasztott gráf eltávolított egy sor az egyes komponens):
Sorok ez a mátrix - a jellemző vektorok az elemi részek, alapját képező a vágások. Mivel a ciklus a tér ortogonális kiegészítője a tér szakaszok, továbbra is találni egy alapvető rendszer megoldások lineáris homogén egyenletek ebben a mátrixban (a mező két elem). Ehhez át szöveg művelet transzformációs mátrix úgy, hogy az első oszlop a részmátrix egység alakult:
Eltávolítja az első négy oszlop, a maradék mátrixot átültetése és rendelje hozzá a megfelelő kt identitás részmátrixának:
Húrok kapott mátrix képviseli alapján ciklusok.