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[уреди]

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.[3] 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,\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.[4]

Skoro drveće[уреди]

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.[5] Neki autori su proučavali parametrizovanu složenost grafova algoritma na r-skoro-drvo, parametrizovanog po r.[6][7]

Reference[уреди]

  1. ^ Berge, Claude (1976), "Broj ciklusa", "Teorija grafova", Glasnik Dover publikacija, 6, Elsevier, p. 27-30, ISBN 9780486419756 .
  2. ^ Berge, Claude (1976), Grafovi i Hipergrafovi, Severno-holandska Matematička biblioteka, 6, Elsevier, p. 477, ISBN 9780720424539 .
  3. ^ Berge, Claude (1976), "Broj ciklusa", "Teorija grafova", Glasnik Dover publikacija, 6, Elsevier, p. 27-30, ISBN 9780486419756 .
  4. ^ 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).
  5. ^ Brualdi, Richard A. (2006), Kombinatorne matrične klase, Enciklopedija matematike i aplikacija, 108, Kembridž: Kembridž univerzitet, p. 349, ISBN 0-521-86565-4, Zbl 1106.05001 
  6. ^ Coppersmith, Don; Vishkin, Uzi (1985), „Rešavanje NP-teških problema u "skoro-drveću": Vertex cover“, Izolovana primljena matematika 10 (1): 27–45, DOI:10.1016/0166-218X(85)90057-5, Zbl 0573.68017 .
  7. ^ Fiala, Jiří; Kloks, Ton; Kratochvíl, Jan (2001), „Fixed-parameter complexity of λ-labelings“, Izolovana primljena matematika 113 (1): 59–72, DOI:10.1016/S0166-218X(00)00387-5, Zbl 0982.05085 .