Gróf csontvázak - ez
gróf csontváz
Legyen G - tetszőleges (n, m) egy K-gráf csatlakoztatott komponensek. Ha G - nem fa, nem tartalmaz (a csatlakoztatott komponensek) vannak ciklusok. Vegyünk egy hurkot, és távolítsa el belőle néhány szélét. A több összekapcsolt komponensek nem emelkedik. Ha ezek után még mindig ciklus, akkor fontolja meg a következő, majd törölni az éle. Továbbra is ezt a folyamatot addig, amíg amíg eltűnnek a ciklus. A kapott részgráf, ami nyilvánvalóan egy erdőben, és ugyanolyan számú csatlakoztatott komponensek, mint az eredeti G gráf, úgynevezett csontváz gráf
Core (kiterjedő) G gráf egy fa, minden fát T, amelynek részleges gráf gráf feszítőfát T egy összefüggő gráf nem egyedileg definiált.
Gráf egy egyedi feszítőfa akkor és csak akkor, ha egy fa.
A csontváz a gráf minimális csatlakoztatva részgráfja G gráf, azaz egy minimális számú élek csúcsokat összekötő.
Részgráfja T G nevezzük a csontváz a gráf, ha ez egy erdő, amely bármely csatlakoztatott komponense G egy fa.
Az élek száma egy tetszőleges G gráf n csúcsú és élek m. k csatlakoztatva komponensek el kellene távolítani, így a mag, független a szekvenciája alapján az eltávolítás és egyenlő m-n + k.
a bizonyítás
Let Hi. i = i, k-összetevői a G gráf, és hagyja, hogy Hi - (ni, MI) -graphs. Eltávolítása után a bordák a ciklusok komponensek Hi ez lesz a fa, amelynek ni -1 bordákkal. Ennélfogva, el kell távolítani a Hi km - (ni -1) élek. Összefoglalva az összes komponens, azt találjuk, hogy a mag a G gráf el kell távolítani (mi -ni +1) = km - ni + 1 = m-n + k bordák, szükség szerint.
meghatározzák
A szám ν (G) = m-n + k nevezzük cyclomatic számát (ciklusos rank) a gráf száma ν * (G) = n-k, azaz az élek száma szerepel semmilyen keret egy G gráf cocyclic rangját. ν (G) + ν * (G) = m. Root fa egy fa T = (V, E) a kijelölt csúcsok ν tartozó V, ahol ν vertex úgynevezett gyökér a fa. Minden csúcsa a gyökér a fa szintje - a lánc hossza a gyökér ehhez a csomóponthoz.
Corollárium 1 gráf G egy erdőben, ha, és csak akkor, ha ν (G) = 0.
Corollárium 2 gráf G egyetlen ciklusban, ha, és csak akkor, ha ν (G) = 1.
Corollárium 3 G gráf, ahol az élek számát nem kevesebb, mint a csúcsok száma egy ciklusban.
Tétel (Kirchhoff)
A magok száma a csatlakoztatott gráf G érdekében n≥2 egyenlő az algebrai kiegészíti minden mátrixelem Kirchhoff K (G) a gráf
Tétel. Digráf erősen összefüggő, ha van egy körút átívelő azt.
Ez a cikk nem vonatkozik a más Wikipédia cikkeket.
Használja a hegyét, és állítsa be a linkeket ajánlásaival összhangban.