Ранг кола

С Википедије, слободне енциклопедије

У математичкој теорији графова, ранг кола, број циклуса,ништа од неусмереног графа је минималан број уклоњених грана из до уклоњених свих циклуса, који чине дрво. За разлику од проблема повратног лука код усмерених графова, лако их је пребројити користећи формулу:

,

где је број грана у , је број чворова и је број повезаних компоненти.[1]

Слични концепти[уреди | уреди извор]

Струјно коло је коранг графичког матроида ,[2] из ког се види да похлепни алгоритам уклања једну по једну грану, у сваком кораку уклања грану која прирада једном циклусу преосталог графа, тражећи уклоњене гране гране из графа . С друге стране (алтернативно), то може бити допуна графа . Број циклуса је такође димензија простора циклуса .[1] Тополошки, се може посматрати као пример једнодимензионог упрошћеног комплекса и њен цyцломатиц број је ранг првог (цео број) хомогена група овог комплекса,

Струјно коло контролише број улазних грана и разлагање графа: у повезаном графу струјно коло ранга свака грана има тачно потомка.[3]

Скоро дрвеће[уреди | уреди извор]

Граф са бројем циклуса се зове р-скоро-дрво, зато што једино гране треба да буду уклоњене да би се направило дрво или стабло. 1-скоро-дрво је скоро-дрво: повезано скоро-дрво је псеудодрво циклус са (могуће тривијално) дрво укорењено у сваки чвор.[4] Неки аутори су проучавали параметризовану сложеност графова алгоритма на р-скоро-дрво, параметризованог по .[5][6]

Референце[уреди | уреди извор]

  1. ^ а б Берге, Цлауде (1976), "Број циклуса", "Теорија графова", Гласник Довер публикација, 6, Елсевиер, стр. 27—30, ИСБН 9780486419756 
  2. ^ Берге, Цлауде (1976), Графови и Хиперграфови, Северно-холандска Математичка библиотека, 6, Елсевиер, стр. 477, ИСБН 9780720424539 
  3. ^ Wхитнеy, Х. (1932), „Не-одвојиви и планарни графови”, Пренос америчког математичког друштва, 34: 339—362 . Посебно погледати Теореме 18 (односе се на разлагање кола) и 19 (о постојању декомпозиције струјног кола).
  4. ^ Бруалди, Рицхард А. (2006), Комбинаторне матричне класе, Енциклопедија математике и апликација, 108, Кембриџ: Кембриџ универзитет, стр. 349, Збл 1106.05001, ISBN 0-521-86565-4 
  5. ^ Цопперсмитх, Дон; Висхкин, Узи (1985), „Решавање НП-тешких проблема у "скоро-дрвећу": Вертеx цовер”, Изолована примљена математика, 10 (1): 27—45, Збл 0573.68017, дои:10.1016/0166-218X(85)90057-5 
  6. ^ Фиала, Јиří; Клокс, Тон; Кратоцхвíл, Јан (2001), „Фиxед-параметер цомплеxитy оф λ-лабелингс”, Изолована примљена математика, 113 (1): 59—72, Збл 0982.05085, дои:10.1016/С0166-218X(00)00387-5