Rang kola

U matematičkoj teoriji grafova, rang kola, broj ciklusa,ništa od neusmerenog grafa $G(x)$ je minimalan broj $r(x)$ uklonjenih grana iz $G(x)$ do uklonjenih svih ciklusa, koji čine drvo. Za razliku od problema povratnog luka kod usmerenih grafova, lako ih je prebrojiti koristeći formulu:

r=m-n+c

,

gde je $m$ broj grana u $G$ , $n$ je broj čvorova i $c$ je broj povezanih komponenti.^[1]

Slični koncepti[uredi | uredi izvor]

Strujno kolo je korang grafičkog matroida $G$ ,^[2] iz kog se vidi da pohlepni algoritam uklanja jednu po jednu granu, u svakom koraku uklanja granu koja prirada jednom ciklusu preostalog grafa, tražeći uklonjene grane grane $r$ iz grafa $G$ . S druge strane (alternativno), to može biti dopuna grafa $G$ . Broj ciklusa je takođe dimenzija prostora ciklusa $G$ .^[1] Topološki, $G$ se može posmatrati kao primer jednodimenzionog uprošćenog kompleksa i njen cyclomatic broj je rang prvog (ceo broj) homogena grupa ovog kompleksa,

r=\operatorname {rank} \left[H_{1}(G,\mathbb {Z} )\right].

Strujno kolo kontroliše broj ulaznih grana i razlaganje grafa: u povezanom grafu strujno kolo ranga $r$ svaka grana ima tačno $r$ potomka.^[3]

Skoro drveće[uredi | uredi izvor]

Graf sa $r$ brojem ciklusa se zove r-skoro-drvo, zato što jedino $r$ grane treba da budu uklonjene da bi se napravilo drvo ili stablo. 1-skoro-drvo je skoro-drvo: povezano skoro-drvo je pseudodrvo ciklus sa (moguće trivijalno) drvo ukorenjeno u svaki čvor.^[4] Neki autori su proučavali parametrizovanu složenost grafova algoritma na r-skoro-drvo, parametrizovanog po $r$ .^[5]^[6]

Reference[uredi | uredi izvor]

^ ^а ^б Berge, Claude (1976), "Broj ciklusa", "Teorija grafova", Glasnik Dover publikacija, 6, Elsevier, стр. 27—30, ISBN 9780486419756
^ Berge, Claude (1976), Grafovi i Hipergrafovi, Severno-holandska Matematička biblioteka, 6, Elsevier, стр. 477, ISBN 9780720424539
^ Whitney, H. (1932), „Ne-odvojivi i planarni grafovi”, Prenos američkog matematičkog društva, 34: 339—362 . Posebno pogledati Teoreme 18 (odnose se na razlaganje kola) i 19 (o postojanju dekompozicije strujnog kola).
^ Brualdi, Richard A. (2006), Kombinatorne matrične klase, Enciklopedija matematike i aplikacija, 108, Kembridž: Kembridž univerzitet, стр. 349, Zbl 1106.05001, ISBN 0-521-86565-4
^ Coppersmith, Don; Vishkin, Uzi (1985), „Rešavanje NP-teških problema u "skoro-drveću": Vertex cover”, Izolovana primljena matematika, 10 (1): 27—45, Zbl 0573.68017, doi:10.1016/0166-218X(85)90057-5
^ Fiala, Jiří; Kloks, Ton; Kratochvíl, Jan (2001), „Fixed-parameter complexity of λ-labelings”, Izolovana primljena matematika, 113 (1): 59—72, Zbl 0982.05085, doi:10.1016/S0166-218X(00)00387-5

[automatski_generisano1-1] а ^б Berge, Claude (1976), "Broj ciklusa", "Teorija grafova", Glasnik Dover publikacija, 6, Elsevier, стр. 27—30, ISBN 9780486419756

[2] Berge, Claude (1976), Grafovi i Hipergrafovi, Severno-holandska Matematička biblioteka, 6, Elsevier, стр. 477, ISBN 9780720424539

[3] Whitney, H. (1932), „Ne-odvojivi i planarni grafovi”, Prenos američkog matematičkog društva, 34: 339—362 . Posebno pogledati Teoreme 18 (odnose se na razlaganje kola) i 19 (o postojanju dekompozicije strujnog kola).

[CMC349-4] Brualdi, Richard A. (2006), Kombinatorne matrične klase, Enciklopedija matematike i aplikacija, 108, Kembridž: Kembridž univerzitet, стр. 349, Zbl 1106.05001, ISBN 0-521-86565-4

[5] Coppersmith, Don; Vishkin, Uzi (1985), „Rešavanje NP-teških problema u "skoro-drveću": Vertex cover”, Izolovana primljena matematika, 10 (1): 27—45, Zbl 0573.68017, doi:10.1016/0166-218X(85)90057-5

[6] Fiala, Jiří; Kloks, Ton; Kratochvíl, Jan (2001), „Fixed-parameter complexity of λ-labelings”, Izolovana primljena matematika, 113 (1): 59—72, Zbl 0982.05085, doi:10.1016/S0166-218X(00)00387-5

[1]

[2]

[3]

[4]

[5]

[6]