Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

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

Кактус (теорія графів)

Кактус (теорія графів)

В теорії графів «кактус» (іноді використовується назва кактусове дерево) — це зв'язний граф, в якому будь-які два прості цикли мають не більше, ніж одну спільну вершину. Еквівалентно, будь-яке ребро в такому графі належить максимум одному простому циклу. Еквівалентно (для нетривіального кактуса), будь-який блок (максимальний підграф без шарнірів) є ребром або циклом.

image
Приклад кактуса

Властивості

Кактуси є зовніпланарними графами. Будь-яке псевдодерево є кактусом.

Сімейство графів, у яких кожна компонента є кактусом, замкнуті за операціями взяття мінора графу. Це сімейство графів можна описати зазначенням єдиного забороненого мінора, «алмаза» з чотирма вершинами, утвореного видаленням ребра з повного графу K4.

Алгоритми та застосування

Деякі задачі про розміщення об'єктів, які є NP-складними для графів загального вигляду, як і деякі інші завдання на графах, можуть бути вирішені за поліноміальний час для кактусів.

Оскільки кактуси є частковими випадками зовніпланарних графів, багато задач комбінаторної оптимізації на графах можуть бути розв'язані за поліноміальний час.

Кактусами подаютьсь електричні кола, які мають корисні застосування. Раннє використання кактусів було пов'язане з поданням операційних підсилювачів.

Кактуси також недавно[] були використані в порівняльній геноміці як засіб подання зв'язків між різними геномами або частинами геномів.

Якщо кактус зв'язний і кожна з його вершин належить не більше ніж двом блокам, його називають декабристом. Будь-який багатогранний граф має підграфом «декабриста», який включає всі вершини графу, — факт, який грає істотну роль у доведенні Лейтона і Мойтри, що будь-який багатогранний граф має [ru] в евклідову площину, в якому вершини отримують координати так, що [en] стає успішним у процесі розсилання повідомлень між усіма парами вершин.

Історія

Кактуси вперше вивчалися під назвою дерево Хусімі, наданою їм Френком Харарі і Джорджем Юджином Уленбеком на честь Коді Хусімі, який працював з цими графами. У тій самій статті використовується назва «кактус» для графів цього типу, в яких будь-який цикл є трикутником, але нині дозволені цикли довільної довжини.

Тим часом назву «дерево Хусімі» стали використовувати для графів, у яких кожен блок є повним графом. Ця назва має мало спільного з роботою Хусімі, і для графів цього сімейства тепер використовується більш доречний термін «блоковий граф», а термін дерево Хусімі використовується все рідше[].

Примітки

  1. El-Mallah, Colbourn, 1988, с. 354–362.
  2. Ben-Moshe, Bhattacharya, Shi, 2005, с. 693–703.
  3. Zmazek, Zerovnik, 2005, с. 536–541.
  4. Корниенко, 1984, с. 215–217.
  5. Nishi, Chua [2], 1986, с. 398–405.
  6. Nishi, Chua [1], 1986, с. 381–397.
  7. Nishi, 1991, с. 766–769.
  8. Paten, Diekhans и др., 2010, с. 410–425.
  9. декабрист — популярний кімнатний вид кактусів
  10. Leighton, Moitra, 2010.
  11. Leighton, Moitra, 2010, с. 686–705.
  12. Harary, Uhlenbeck, 1953, с. 315–322.
  13. Husimi, 1950, с. 682–684.

Література

  • Ehab El-Mallah, Charles J. Colbourn. The complexity of some edge deletion problems // IEEE Transactions on Circuits and Systems. — 1988. — Т. 35, вип. 3. — С. 354–362. — DOI:10.1109/31.1748.
  • Boaz Ben-Moshe, Binay Bhattacharya, Qiaosheng Shi. Algorithms and Computation, 16th Int. Symp., ISAAC 2005. — Springer-Verlag, 2005. — Т. 3827. — С. 693–703. — (). — DOI:10.1007/11602613_70.
  • Blaz Zmazek, Janez Zerovnik. Ninth International Conference on Information Visualisation (IV'05). — 2005. — С. 536–541. — . — DOI:10.1109/IV.2005.48.
  • Н.М. Корниенко. Комбинаторные алгоритмы на классе графов // Известия Национальной академии наук Беларуси СЕРИЯ ФИЗИКО-ТЕХНИЧЕСКИХ НАУК. — 1984. — Вип. 3. — С. 109-111.
  • Tetsuo Nishi, Leon O. Chua. Topological proof of the Nielsen-Willson theorem // IEEE Transactions on Circuits and Systems. — 1986. — Т. 33, вип. 4. — С. 398–405. — DOI:10.1109/TCS.1986.1085935.
  • Tetsuo Nishi, Leon O. Chua. Uniqueness of solution for nonlinear resistive circuits containing CCCS’s or VCVS’s whose controlling coefficients are finite // IEEE Transactions on Circuits and Systems. — 1986. — Т. 33, вип. 4. — С. 381–397. — DOI:10.1109/TCS.1986.1085934.
  • Tetsuo Nishi. Proceedings of the IEEE International Symposium on Circuits and Systems, Singapore. — 1991. — С. 766–769.
  • Benedict Paten, Mark Diekhans, Dent Earl, John St. John, Jian Ma, Bernard Suh, David Haussler. Research in Computational Molecular Biology // Lecture Notes in Computer Science. — 2010. — Т. 6044. — С. 410–425. — . — DOI:10.1007/978-3-642-12683-3_27.
  • Tom Leighton, Ankur Moitra. Some Results on Greedy Embeddings in Metric Spaces // . — 2010. — Т. 44, вип. 3. — С. 686–705. — DOI:10.1007/s00454-009-9227-6.
  • Frank Harary, George E. Uhlenbeck. On the number of Husimi trees, I // Proceedings of the National Academy of Sciences. — 1953. — Т. 39, вип. 4. — С. 315–322. — DOI:10.1073/pnas.39.4.315.
  • Kodi Husimi. Note on Mayers' theory of cluster integrals // Journal of Chemical Physics. — 1950. — Т. 18, вип. 5. — С. 682–684. — DOI:10.1063/1.1747725.

Посилання

  • Application of Cactus Graphs in Analysis and Design [ 6 серпня 2019 у Wayback Machine.] of Electronic Circuits

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

V teoriyi grafiv kaktus inodi vikoristovuyetsya nazva kaktusove derevo ce zv yaznij graf v yakomu bud yaki dva prosti cikli mayut ne bilshe nizh odnu spilnu vershinu Ekvivalentno bud yake rebro v takomu grafi nalezhit maksimum odnomu prostomu ciklu Ekvivalentno dlya netrivialnogo kaktusa bud yakij blok maksimalnij pidgraf bez sharniriv ye rebrom abo ciklom Priklad kaktusaVlastivostiKaktusi ye zovniplanarnimi grafami Bud yake psevdoderevo ye kaktusom Simejstvo grafiv u yakih kozhna komponenta ye kaktusom zamknuti za operaciyami vzyattya minora grafu Ce simejstvo grafiv mozhna opisati zaznachennyam yedinogo zaboronenogo minora almaza z chotirma vershinami utvorenogo vidalennyam rebra z povnogo grafu K4 Algoritmi ta zastosuvannyaDeyaki zadachi pro rozmishennya ob yektiv yaki ye NP skladnimi dlya grafiv zagalnogo viglyadu yak i deyaki inshi zavdannya na grafah mozhut buti virisheni za polinomialnij chas dlya kaktusiv Oskilki kaktusi ye chastkovimi vipadkami zovniplanarnih grafiv bagato zadach kombinatornoyi optimizaciyi na grafah mozhut buti rozv yazani za polinomialnij chas Kaktusami podayuts elektrichni kola yaki mayut korisni zastosuvannya Rannye vikoristannya kaktusiv bulo pov yazane z podannyam operacijnih pidsilyuvachiv Kaktusi takozh nedavno koli buli vikoristani v porivnyalnij genomici yak zasib podannya zv yazkiv mizh riznimi genomami abo chastinami genomiv Yaksho kaktus zv yaznij i kozhna z jogo vershin nalezhit ne bilshe nizh dvom blokam jogo nazivayut dekabristom Bud yakij bagatogrannij graf maye pidgrafom dekabrista yakij vklyuchaye vsi vershini grafu fakt yakij graye istotnu rol u dovedenni Lejtona i Mojtri sho bud yakij bagatogrannij graf maye ru v evklidovu ploshinu v yakomu vershini otrimuyut koordinati tak sho en staye uspishnim u procesi rozsilannya povidomlen mizh usima parami vershin IstoriyaKaktusi vpershe vivchalisya pid nazvoyu derevo Husimi nadanoyu yim Frenkom Harari i Dzhordzhem Yudzhinom Ulenbekom na chest Kodi Husimi yakij pracyuvav z cimi grafami U tij samij statti vikoristovuyetsya nazva kaktus dlya grafiv cogo tipu v yakih bud yakij cikl ye trikutnikom ale nini dozvoleni cikli dovilnoyi dovzhini Tim chasom nazvu derevo Husimi stali vikoristovuvati dlya grafiv u yakih kozhen blok ye povnim grafom Cya nazva maye malo spilnogo z robotoyu Husimi i dlya grafiv cogo simejstva teper vikoristovuyetsya bilsh dorechnij termin blokovij graf a termin derevo Husimi vikoristovuyetsya vse ridshe proyasniti PrimitkiEl Mallah Colbourn 1988 s 354 362 Ben Moshe Bhattacharya Shi 2005 s 693 703 Zmazek Zerovnik 2005 s 536 541 Kornienko 1984 s 215 217 Nishi Chua 2 1986 s 398 405 Nishi Chua 1 1986 s 381 397 Nishi 1991 s 766 769 Paten Diekhans i dr 2010 s 410 425 dekabrist populyarnij kimnatnij vid kaktusiv Leighton Moitra 2010 Leighton Moitra 2010 s 686 705 Harary Uhlenbeck 1953 s 315 322 Husimi 1950 s 682 684 LiteraturaEhab El Mallah Charles J Colbourn The complexity of some edge deletion problems IEEE Transactions on Circuits and Systems 1988 T 35 vip 3 S 354 362 DOI 10 1109 31 1748 Boaz Ben Moshe Binay Bhattacharya Qiaosheng Shi Algorithms and Computation 16th Int Symp ISAAC 2005 Springer Verlag 2005 T 3827 S 693 703 DOI 10 1007 11602613 70 Blaz Zmazek Janez Zerovnik Ninth International Conference on Information Visualisation IV 05 2005 S 536 541 ISBN 0 7695 2397 8 DOI 10 1109 IV 2005 48 N M Kornienko Kombinatornye algoritmy na klasse grafov Izvestiya Nacionalnoj akademii nauk Belarusi SERIYa FIZIKO TEHNIChESKIH NAUK 1984 Vip 3 S 109 111 Tetsuo Nishi Leon O Chua Topological proof of the Nielsen Willson theorem IEEE Transactions on Circuits and Systems 1986 T 33 vip 4 S 398 405 DOI 10 1109 TCS 1986 1085935 Tetsuo Nishi Leon O Chua Uniqueness of solution for nonlinear resistive circuits containing CCCS s or VCVS s whose controlling coefficients are finite IEEE Transactions on Circuits and Systems 1986 T 33 vip 4 S 381 397 DOI 10 1109 TCS 1986 1085934 Tetsuo Nishi Proceedings of the IEEE International Symposium on Circuits and Systems Singapore 1991 S 766 769 Benedict Paten Mark Diekhans Dent Earl John St John Jian Ma Bernard Suh David Haussler Research in Computational Molecular Biology Lecture Notes in Computer Science 2010 T 6044 S 410 425 ISBN 978 3 642 12682 6 DOI 10 1007 978 3 642 12683 3 27 Tom Leighton Ankur Moitra Some Results on Greedy Embeddings in Metric Spaces 2010 T 44 vip 3 S 686 705 DOI 10 1007 s00454 009 9227 6 Frank Harary George E Uhlenbeck On the number of Husimi trees I Proceedings of the National Academy of Sciences 1953 T 39 vip 4 S 315 322 DOI 10 1073 pnas 39 4 315 Kodi Husimi Note on Mayers theory of cluster integrals Journal of Chemical Physics 1950 T 18 vip 5 S 682 684 DOI 10 1063 1 1747725 PosilannyaApplication of Cactus Graphs in Analysis and Design 6 serpnya 2019 u Wayback Machine of Electronic Circuits

Дата публікації:
Топ