Цикл (теорія графів)

Матеріал з Вікіпедії - вільної енциклопедії

В теорії графів два типи об'єктів зазвичай називаються циклами.

Один тип циклів. частіше називаються замкнутим обходом. складається з послідовності вершин, що починається і закінчується в тій же самій вершині, і кожні два послідовні вершини в послідовності суміжні. Інший тип циклів, іноді званих простими циклами. - це замкнуті обходи без повторного проходу по ребру або відвідування вершини двічі, за винятком початкової і кінцевої вершин. Прості цикли можна описати набором ребер, на відміну від замкнутих обходів, в яких набори ребер (з можливим повторенням) не визначають однозначно порядок вершин. Орієнтований цикл в орграфе - це послідовність вершин, що починається і завершується в тій же самій вершині, і в цій послідовності для будь-яких двох послідовних вершин існує дуга з більш ранньої в більш пізню. Таке ж відмінність між простими циклами і обходами, як вище, можна визначити і для орієнтованих графів # 91; 1 # 93 ;.

Цикли без хорд

Цикл без хорд в графі, також званий дірою або породженим циклом, - це цикл, в якому ніякі дві вершини циклу не з'єднані ребром, хіба що це ребро саме належить циклу. Антідира - це доповнення діри. Графи без хорд можна використовувати для опису досконалих графів - відповідно до суворої теоремі про вчинені графах [en] граф є досконалим в тому і тільки в тому випадку, коли він не містить дірок і антідир з непарним числом вершин більше трьох. Хордальний граф - це спеціальний тип скоєних графів, в якому немає дірок розміром більше трьох.

Обхват графа - це довжина найменшого циклу. Цей цикл обов'язково не матиме хорд. Клітини - це найменші регулярні графи з заданим ступенем вершин і обхватом.

Периферійний цикл [en] - це цикл в графі з властивістю, що будь-які два ребра, які не належать циклу, можна з'єднати шляхом внутрішні точки якого не належать циклу. У графі, що не утвореному додаванням одного ребра до циклу, периферійний цикл повинен бути породженим циклом.

простір циклів

Поняття цикл може також ставитися до елементів простору циклів [en] графа. Воно складається з безлічі ребер, які мають парну ступінь для кожної вершини. Безлічі утворюють векторний простір над кінцевим полем з двох елементів. Використовуючи методи алгебраїчної топології його можна узагальнити до векторних просторів або модулів над іншими кільцями. такими як цілі числа, дійсні числа і т. д. По теоремі Веблена будь-який елемент простору циклів можна отримати шляхом комбінування простих циклів. База циклів графа - це безліч простих циклів, які утворюють базис простору циклів # 91; 2 # 93; # 91; 3 # 93 ;.

Пошук циклу

Неорієнтовані граф має цикл в тому і тільки в тому випадку, коли пошук в глибину (DFS) знаходить ребро, яке призводить до вже відвіданих вершині (зворотна дуга) # 91; 4 # 93 ;. Таким же чином, всі зворотні ребра, які алгоритм DFS виявляє, є частинами циклів # 91; 5 # 93 ;. Для неорієнтованих графів потрібно тільки час O (n) для знаходження циклу в графі з n вершинами, оскільки максимум n - 1 ребер можуть бути ребрами дерева.

Орієнтований граф має цикл в тому і тільки в тому випадку, коли DFS знаходить зворотний дугу. Дуги вперед і поперечні дуги не обов'язково говорять про циклі. Багато алгоритми топологічних угруповань також виявляють цикли, оскільки вони заважають існуванню топологічного порядку. Якщо орієнтований граф розділений на компоненти сильної зв'язності. цикли існують тільки в компонентах, але не між ними, оскільки цикли сильно зв'язні # 91; 5 # 93 ;.

Додатки алгоритмів знаходження циклів включають графи очікування для знаходження взаємних блокувань в системах з паралельними потоками # 91; 6 # 93 ;.

Покриття графів циклами

У роботі 1736 року про проблеми семи мостів Кенігсберга. загальноприйнято вважається днем ​​народження теорії графів, Леонард Ейлер довів, що для того, щоб кінцевий неорієнтований граф мав замкнутий обхід всіх ребер рівно по одному разу, необхідно і достатньо, щоб він був зв'язний і мав парну ступінь всіх вершин. Відповідний опис існування замкнутого обходу кожного ребра рівно один раз в орієнтованому графі полягає у вимозі, щоб граф був сильно зв'язний і кожна вершина мала однакове число вхідних і вихідних дуг. В обох випадках отриманий шлях відомий як Ейлером цикл. Якщо кінцевий неорієнтований граф має парну ступінь кожної вершини, незалежно від того, зв'язний він чи ні, можна знайти безліч простих циклів, які покривають кожне ребро рівно раз - це Теоремі Веблена # 91; 7 # 93 ;. Якщо зв'язний граф не задовольняє умовам теореми Ейлера, замкнутий обхід мінімальної довжини, що покриває всі ребра щонайменше один раз може бути знайдений, проте, за поліноміальний час шляхом вирішення задачі про інспекцію доріг [en].

Гіпотеза про подвійне покритті циклами стверджує, що для будь-якого графа без мостів існує мультімножество простих циклів, що покривають кожне ребро графа в точності два рази. Доказ гіпотези, або контрприклад поки не знайдені # 91; 10 # 93 ;.

Класи графів, які визначаються циклами

Деякі важливі класи графів можна визначити або описати їх циклами. це:

• Двочастковий граф - граф без непарних циклів.
• Кактус. - граф, в якому будь-яка нетривіальна двусвязного компонента є циклом.
• Граф-цикл - граф, що складається з єдиного циклу.
• Хордальний граф - граф, в якому немає породжених циклів довжиною більше трьох.
• Орієнтований ациклічний граф - орієнтований граф без циклів.
• Досконалий граф - граф без породжених циклів непарної довжини більше трьох, або їх доповнень.
• Псевдолес. - граф, в якому кожна зв'язкова компонента має максимум один цикл.
• Сильно зв'язний граф - орієнтований граф, в якому будь-яка дуга входить в будь-якої цикл.
• Граф без трикутників - граф, в якому немає циклів довжини три.

Напишіть відгук про статтю "Цикл (теорія графів)"

Примітки

: Невірне або відсутнє зображення

Для поліпшення цієї статті бажано? :

• Перевірити якість перекладу з іноземної мови.

Уривок, що характеризує Цикл (теорія графів)

- Так ось хоч би щодо дров або кормів, доповім вам. Адже ми від Свенцяни відступали, не смій лозини торкнути, або сенца там, або що. Адже ми йдемо, йому дістається, чи не так, ваша світлість? - звернувся він до свого князя, - а ти не смій. У нашому полку під суд двох офіцерів віддали за такі справи. Ну, як ясновельможний надійшов, так щодо цього просто стало. Світло побачили ...
- Так чому ж він забороняв?
Тимохін зніяковіло озирався, не розуміючи, як і що відповідати на таке питання. П'єр з тим же питанням звернувся до князя Андрія.
- А щоб не розоряти край, який ми залишали ворогові, - злобно глузливо сказав князь Андрій. - Це дуже грунтовно; не можна дозволяти грабувати край і привчатися військам до мародерства. Ну і в Дружковкае він теж правильно розсудив, що французи можуть обійти нас і що у них більше сил. Але він не міг зрозуміти того, - раптом як би вирвався тонким голосом закричав князь Андрій, - але він не міг зрозуміти, що ми в перший раз билися там за російську землю, що у військах був такий дух, якого ніколи я не бачив, що ми два дні підряд відбивали французів і що цей успіх подесятеряє наші сили. Він велів відступати, і всі зусилля і втрати були марними. Він не думав про зраду, він намагався все зробити якнайкраще, він все обдумав; але від цього то він і не годиться. Він не годиться тепер саме тому, що він все обдумує дуже грунтовно і акуратно, як і слід кожному німцю. Як би тобі сказати ... Ну, у батька твого німець лакей, і він прекрасний лакей і задовольнить всім його потребам краще тебе, і нехай він служить; але якщо батько при смерті хворий, ти проженеш лакея і своїми незвичними, незграбними руками станеш ходити за батьком і краще заспокоїш його, ніж майстерний, але чужа людина. Так і зробили з Барклаем. Поки Україна була здорова, їй міг служити чужій, і був прекрасний міністр, але як тільки вона в небезпеці; потрібна своя, рідна людина. А у вас в клубі вигадали, що він зрадник! Тим, що його обмовили зрадником, зроблять тільки те, що потім, засоромившись свого помилкового нарікання, з зрадників зроблять раптом героєм або генієм, що ще буде несправедливі. Він чесний і дуже акуратний німець ...
- Однак, кажуть, він вправний полководець, - сказав П'єр.
- Я не розумію, що таке значить майстерний полководець, - з насмішкою сказав князь Андрій.
- Майстерний полководець, - сказав П'єр, - ну, той, який передбачав всі випадковості ... ну, вгадав думки противника.
- Так це неможливо, - сказав князь Андрій, як ніби про давно вирішена справа.
П'єр здивовано глянув на нього.
- Однак, - сказав він, - адже говорять же, що війна подібна шаховій грі.
- Так, - сказав князь Андрій, - тільки з тою маленькою різницею, що в шахах над кожним кроком ти можеш думати скільки завгодно, що ти там поза умов часу, і ще з тією різницею, що кінь завжди сильніше пішаки і дві пішаки завжди сильніше однієї, a на війні один батальйон іноді сильніше дивізії, а іноді слабкіше роти. Відносна сила військ нікому не може бути відома. Повір мені, - сказав він, - що якби що залежало від розпоряджень штабів, то я б був там і робив би розпорядження, а замість того я маю честь служити тут, в полку ось з цими панами, і вважаю, що від нас дійсно буде залежати завтрашній день, а не від них ... Успіх ніколи не залежав і не буде залежати ні від позиції, ні від озброєння, ні навіть від числа; а вже найменше від позиції.
- А від чого ж?
- Від того почуття, яке є в мені, в ньому, - він вказав на Тимохіна, - у кожному солдата.
Князь Андрій глянув на Тимохіна, який злякано і дивуючись дивився на свого командира. У противность своєї колишньої стриманою мовчазності князь Андрій здавався тепер схвильованим. Він, мабуть, не міг втриматися від висловлення тих думок, які несподівано приходили йому.
- Бій виграє той, хто твердо вирішив його виграти. Чому ми під Аустерліцем програли війну? У нас втрата була майже рівна з французами, але ми сказали собі дуже рано, що ми програли бій, - і програли. А сказали ми це тому, що нам там нема чого було битися: скоріше хотілося піти з поля бою. «Програли - ну так бігти!» - ми і побігли. Якщо б до вечора ми не говорили цього, бог знає що б було. А завтра ми цього не скажемо. Ти говориш: наша позиція, лівий фланг слабкий, правий фланг розтягнутий, - продовжував він, - все це дурниця, нічого цього немає. А що нам належить завтра? Сто мільйонів найрізноманітніших випадковостей, які будуть вирішуватися миттєво тим, що побігли або побіжать вони або наші, що вб'ють того, вб'ють іншого; а то, що робиться тепер, - все це забава. Справа в тому, що ті, з ким ти їздив по позиції, не тільки не сприяють загальному ходу справ, але заважають йому. Вони зайняті тільки своїми маленькими інтересами.
- В таку хвилину? - докірливо сказав П'єр.
- В таку хвилину, - повторив князь Андрій, - для них це тільки така хвилина, в яку можна підкопатися під ворога і отримати зайвий хрестик або стрічку. Для мене на завтра ось що: стотисячне російське і стотисячне французьке війська зійшлися битися, і факт в тому, що ці двісті тисяч б'ються, і хто буде злей битися і себе менше жаліти, той переможе. І хочеш, я тобі скажу, що, що б там не було, що б не плутали там угорі, ми виграємо бій завтра. Завтра, що б там не було, ми виграємо бій!
- Ось, ваша світлість, правда, правда істинна, - промовив Тимохін. - Що себе жаліти тепер! Солдати в моєму батальйоні, повірите чи, не стали горілку, пити: не такий день, кажуть. - Все помовчали.
Офіцери піднялися. Князь Андрій вийшов з ними за сарай, віддаючи останні накази ад'ютантові. Коли офіцери пішли, П'єр підійшов до князя Андрія і тільки що хотів почати розмову, як по дорозі недалеко від сараю застукали копита трьох коней, і, глянувши за цим напрямком, князь Андрій дізнався Вольцогена з Клаузевіца, що супроводжується козаком. Вони близько проїхали, продовжуючи розмовляти, і П'єр з Андрієм мимоволі почули такі фрази:
- Der Krieg muss im Raum verlegt werden. Der Ansicht kann ich nicht genug Preis geben, [Війна повинна бути перенесена в простір. Цей погляд я не можу досить возвеличити (нім.)] - говорив один.
- O ja, - сказав інший голос, - da der Zweck ist nur den Feind zu schwachen, so kann man gewiss nicht den Verlust der Privatpersonen in Achtung nehmen. [О так, так як мета полягає в тому, щоб послабити ворога, то не можна брати до уваги втрати приватних осіб (нім.)]
- O ja, [О так (нім.)] - підтвердив перший голос.
- Так, im Raum verlegen, [перенести в простір (нім.)] - повторив, злобно фиркаючи носом, князь Андрій, коли вони проїхали. - Im Raum то [В просторі (нім.)] У мене залишився батько, і син, і сестра в Лисих Горах. Йому це все одно. Ось воно те, що я тобі казав, - ці панове німці завтра не виграють бій, а тільки напаскудити, скільки їх сил буде, тому що в його німецької голові тільки міркування, не варті виїденого яйця, а в серці немає того, що одне тільки і потрібно на завтра, - то, що є в Тимохін. Вони всю Європу віддали йому і приїхали нас вчити - славні вчителі! - знову заверещав його голос.
- Так ви думаєте, що завтрашнє бій буде виграно? - сказав П'єр.
- Так, так, - неуважно сказав князь Андрій. - Одне, що б я зробив, якби мав владу, - почав він знову, - я не брав би полонених. Що таке полонені? Це лицарство. Французи розорили мій будинок і йдуть розорити Москву, і образили і ображають мене всяку секунду. Вони вороги мої, вони злочинці все, за моїми поняттями. І так само думає Тимохін і вся армія. Треба їх стратити. Якщо вони вороги мої, то не можуть бути друзями, як би вони там не розмовляли в Тільзіті.
- Так, так, - промовив П'єр, блискучими очима дивлячись на князя Андрія, - я зовсім, зовсім згоден з вами!
Те питання, яке з Можайський гори і на весь цей день турбував П'єра, тепер представився йому абсолютно ясним і цілком дозволеним. Він зрозумів тепер весь сенс і все значення цієї війни і майбутнього бою. Все, що він бачив у цей день, всі значні, строгі вирази облич, які він мигцем бачив, освітилися для нього новим світлом. Він зрозумів ту приховану (latente), як то кажуть у фізиці, теплоту патріотизму, яка була у всіх тих людей, яких він бачив, і яка пояснювала йому то, навіщо всі ці люди спокійно і ніби легковажно готувалися до смерті.
- Не брати полонених, - продовжував князь Андрій. - Це одне змінило б всю війну і зробило б її менш жорстокою. А то ми грали у війну - ось що погано, ми велікодушнічаем тощо. Це велікодушнічанье і чутливість - на зразок великодушності і чутливості барині, з якої робиться нудота, коли вона бачить убиваемого теляти; вона так добра, що не може бачити кров, але вона з апетитом їсть цього теляти під соусом. Нам тлумачать про права війни, про лицарство, про парламентерстве, щадити нещасних і так далі. Все дурниця. Я бачив в 1805 році лицарство, парламентерство: нас надули, ми надули. Грабують чужі будинки, пускають фальшиві асигнації, та найгірше - вбивають моїх дітей, мого батька і говорять про правила війни й довготерпіння до ворогів. Не брати полонених, а вбивати і йти на смерть! Хто дійшов до цього так, як я, тими ж стражданнями ...