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

Гусениця або гусеничне дерево це дерево в якому всі вершини розташовані на відстані 1 від центрального шляху Гусениця Гр

Гусениця (теорія графів)

Гусениця (теорія графів)

Гусениця або гусеничне дерево — це дерево, в якому всі вершини розташовані на відстані 1 від центрального шляху.

image
Гусениця

Графи-гусениці першими почали вивчати в серії статей Харарі та . Назву запропонував [en]. Як барвисто писали Харарі та Швенк, «Гусениця — це дерево, яке перетворюється в шлях, якщо видалити кокон з кінцевих вершин».

Еквівалентні описи

Такі характеристики описують графи-гусениці:

  • Це дерева, в яких видалення листків разом з ребрами дає шлях.
  • Це дерева, в яких існує шлях, що містить всі вершини степеня два і більше.
  • Це дерева, в яких будь-яка вершина степеня три і більше має не більше двох сусідів, які не є листками.
  • Це дерева, які не містять в якості підграфів граф, утворений заміною кожного ребра зірки K1,3 шляхом з двох ребер.
  • Це зв'язні графи, які можна намалювати, розташувавши вершини на двох паралельних прямих з ребрами, що не перетинаються, а кінцеві вершини кожного ребра розташувавши на різних прямих.
  • Це дерева, квадрат яких є гамільтоновим графом. Під квадратом тут мається на увазі існування циклічної послідовності всіх вершин, при якій кожна пара сусідніх вершин у послідовності знаходяться на відстані один або два. Дерева, що не є гусеницями, такої послідовності не мають. Цикл такого вигляду можна отримати, якщо намалювати гусеницю з вершинами на двох паралельних прямих. Потім нумеруємо вершини на одній прямій в одному напрямку, а на іншій прямій — у зворотному напрямку.
  • Це дерева, реберні графи яких містять гамільтонів шлях. Такий шлях може бути отриманий шляхом впорядкування ребер на малюнку гусениці з двома прямими. Більш загально, число ребер, які потрібно додати до реберного графу для довільного дерева, щоб він містив гамільтонів шлях (розмір його гамільтонового доповнення), дорівнює мінімальному числу гусениць, що не перетинаються по ребрах, на які дерево може бути розбите.
  • Це зв'язні графи з одиничною шляховою шириною.
  • Це зв'язні інтервальні графи без трикутників.

Узагальнення

K-дерево — це хордальний граф, що містить рівно n − k максимальних клік, кожна з яких містить k + 1 вершину. В k-дереві, яке саме по собі не є (k + 1)-клікою, кожна максимальна кліка або поділяє граф на дві або більше компонент, або містить (k-)листкову вершину, яка належить тільки одній максимальній кліці. k-шлях — це k-дерево з максимум двома листками, а k-гусениця — це k-дерево, яке можна розбити на k-шляхи і кілька k-листків, кожен з яких суміжний з сепаратором k-кліки k-шляху. В цій термінології, 1-гусениця — це те ж саме, що й граф-гусениця, а k-гусениці є реберно-максимальними графами зі шляховою шириною k.

Краб — це дерево, в якому всі вершини знаходяться на відстані, що не перевершує 2 від центрального шляху

Перерахування

Гусениці є рідкісним випадком задач перерахування графів, коли відома точна формула — якщо n ≥ 3, число гусениць з n вершинами дорівнює

image

Для n = 1, 2, 3, …число гусениць з n вершинами дорівнює

1, 1, 1, 2, 3, 6, 10, 20, 36, 72, 136, 272, 528, 1056, 2080, 4160, … (послідовність A005418 з Онлайн енциклопедії послідовностей цілих чисел, OEIS).

Обчислювальна складність

Пошук стягувальної гусениці є NP-повною задачею. Відповідна оптимізаційна задача — задача про мінімальну стягувальну гусеницю (ЗМСГ), в якій задані ціни на ребрах і метою є пошук гусениці, яка мінімізує ціни. Тут ціна гусениці визначається як сума цін її ребер, а кожне ребро має дві ціни, в залежності від того, є воно листком чи внутрішнім ребром. Не існує f(n)-апроксимаційного алгоритму для ЗМСГ, якщо не виконується P = NP. Тут f(n) — будь-яка функція від n, що обчислюється за поліноміальний час, а n — число вершин графу.

Існує параметризований алгоритм, який знаходить оптимальний розв'язок ЗМСГ у графі з обмеженою шириною дерева. Таким чином, завдання про стягувальну гусеницю, так і задача про мінімальну стягувальну гусеницю мають алгоритми лінійного часу, якщо граф зовніпланарний, є паралельно-послідовним графом, або графом Халіна.

Застосування

Гусениці використовуються в хімічній теорії графів для подання структури молекул бензоїдних вуглеводнів. У цьому поданні молекули утворюють гусениці, в яких кожне ребро відповідає кільцю з 6 атомів вуглецю, а два ребра інцидентні вершині, якщо відповідні бензольні кільця належать послідовності сполучених лінійно кілець. (англ. Sherif El-Basil) пише: «Дивно, що майже всі графи, які відіграють важливу роль у тому, що зараз називається „хімічною теорією графів“, пов'язані з графами-гусеницями». У цьому контексті графи-гусениці відомі також як бензоїдні дерева або дерева Гутмана, за роботами Івана Гутмана в цій галузі.

Див. також

Примітки

  1. Harary, Schwenk, 1973, с. 359–365.
  2. El-Basil, 1987, с. 153–174.
  3. Harary, Schwenk, 1973.
  4. Harary, Schwenk, 1971, с. 138–140.
  5. Harary, Schwenk, 1972, с. 203–209.
  6. Raychaudhuri, 1995, с. 299–306.
  7. Proskurowski, Telle, 1999, с. 167–176.
  8. Eckhoff, 1993, с. 117–127.
  9. Weisstein, Eric W. Lobster(англ.) на сайті Wolfram MathWorld.
  10. Khosravani, 2011.
  11. Gutman, 1977, с. 309–315.
  12. El-Basil, 1990, с. 273–289.

Література

  • Masoud Khosravani. Searching for optimal caterpillars in general and bounded treewidth graphs // Ph.D.. — 2011.
  • Sherif El-Basil. Applications of caterpillar trees in chemistry and physics // Journal of Mathematical Chemistry. — 1987. — Т. 1, вип. 2. — С. 153–174. — DOI:10.1007/BF01205666.
  • Ivan Gutman. Topological properties of benzenoid systems // Theoretica Chimica Acta. — 1977. — Т. 45, вип. 4. — С. 309–315. — DOI:10.1007/BF00554539.
  • Sherif El-Basil. Advances in the Theory of Benzenoid Hydrocarbons. — 1990. — Т. 153. — С. 273–289. — DOI:10.1007/3-540-51505-4_28.
  • Andrzej Proskurowski, Jan Arne Telle. Classes of graphs with restricted interval models // Discrete Mathematics and Theoretical Computer Science. — 1999. — Т. 3. — С. 167–176.
  • Arundhati Raychaudhuri. The total interval number of a tree and the Hamiltonian completion number of its line graph // Information Processing Letters. — 1995. — Т. 56, вип. 6. — С. 299–306. — DOI:10.1016/0020-0190(95)00163-8.
  • Jürgen Eckhoff. Extremal interval graphs // Journal of Graph Theory. — 1993. — Т. 17, вип. 1. — С. 117–127. — DOI:10.1002/jgt.3190170112.
  • Frank Harary, Allen J. Schwenk. Trees with Hamiltonian square // Mathematika. — 1971. — Т. 18. — С. 138–140. — DOI:10.1112/S0025579300008494.
  • Frank Harary, Allen J. Schwenk. A new crossing number for bipartite graphs // Utilitas Math.. — 1972. — Т. 1. — С. 203–209.
  • Frank Harary, Allen J. Schwenk. The number of caterpillars // Discrete Mathematics. — 1973. — Т. 6, вип. 4. — С. 359–365. — DOI:10.1016/0012-365x(73)90067-8.

Посилання

  • Weisstein, Eric W. Caterpillar(англ.) на сайті Wolfram MathWorld.

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

Gusenicya abo gusenichne derevo ce derevo v yakomu vsi vershini roztashovani na vidstani 1 vid centralnogo shlyahu Gusenicya Grafi gusenici pershimi pochali vivchati v seriyi statej Harari ta Nazvu zaproponuvav en Yak barvisto pisali Harari ta Shvenk Gusenicya ce derevo yake peretvoryuyetsya v shlyah yaksho vidaliti kokon z kincevih vershin Ekvivalentni opisiTaki harakteristiki opisuyut grafi gusenici Ce dereva v yakih vidalennya listkiv razom z rebrami daye shlyah Ce dereva v yakih isnuye shlyah sho mistit vsi vershini stepenya dva i bilshe Ce dereva v yakih bud yaka vershina stepenya tri i bilshe maye ne bilshe dvoh susidiv yaki ne ye listkami Ce dereva yaki ne mistyat v yakosti pidgrafiv graf utvorenij zaminoyu kozhnogo rebra zirki K1 3 shlyahom z dvoh reber Ce zv yazni grafi yaki mozhna namalyuvati roztashuvavshi vershini na dvoh paralelnih pryamih z rebrami sho ne peretinayutsya a kincevi vershini kozhnogo rebra roztashuvavshi na riznih pryamih Ce dereva kvadrat yakih ye gamiltonovim grafom Pid kvadratom tut mayetsya na uvazi isnuvannya ciklichnoyi poslidovnosti vsih vershin pri yakij kozhna para susidnih vershin u poslidovnosti znahodyatsya na vidstani odin abo dva Dereva sho ne ye gusenicyami takoyi poslidovnosti ne mayut Cikl takogo viglyadu mozhna otrimati yaksho namalyuvati gusenicyu z vershinami na dvoh paralelnih pryamih Potim numeruyemo vershini na odnij pryamij v odnomu napryamku a na inshij pryamij u zvorotnomu napryamku Ce dereva reberni grafi yakih mistyat gamiltoniv shlyah Takij shlyah mozhe buti otrimanij shlyahom vporyadkuvannya reber na malyunku gusenici z dvoma pryamimi Bilsh zagalno chislo reber yaki potribno dodati do rebernogo grafu dlya dovilnogo dereva shob vin mistiv gamiltoniv shlyah rozmir jogo gamiltonovogo dopovnennya dorivnyuye minimalnomu chislu gusenic sho ne peretinayutsya po rebrah na yaki derevo mozhe buti rozbite Ce zv yazni grafi z odinichnoyu shlyahovoyu shirinoyu Ce zv yazni intervalni grafi bez trikutnikiv UzagalnennyaK derevo ce hordalnij graf sho mistit rivno n k maksimalnih klik kozhna z yakih mistit k 1 vershinu V k derevi yake same po sobi ne ye k 1 klikoyu kozhna maksimalna klika abo podilyaye graf na dvi abo bilshe komponent abo mistit k listkovu vershinu yaka nalezhit tilki odnij maksimalnij klici k shlyah ce k derevo z maksimum dvoma listkami a k gusenicya ce k derevo yake mozhna rozbiti na k shlyahi i kilka k listkiv kozhen z yakih sumizhnij z separatorom k kliki k shlyahu V cij terminologiyi 1 gusenicya ce te zh same sho j graf gusenicya a k gusenici ye reberno maksimalnimi grafami zi shlyahovoyu shirinoyu k Krab ce derevo v yakomu vsi vershini znahodyatsya na vidstani sho ne perevershuye 2 vid centralnogo shlyahuPererahuvannyaGusenici ye ridkisnim vipadkom zadach pererahuvannya grafiv koli vidoma tochna formula yaksho n 3 chislo gusenic z n vershinami dorivnyuye 2 n 4 2 n 4 2 displaystyle 2 n 4 2 lfloor n 4 2 rfloor Dlya n 1 2 3 chislo gusenic z n vershinami dorivnyuye 1 1 1 2 3 6 10 20 36 72 136 272 528 1056 2080 4160 poslidovnist A005418 z Onlajn enciklopediyi poslidovnostej cilih chisel OEIS Obchislyuvalna skladnistPoshuk styaguvalnoyi gusenici ye NP povnoyu zadacheyu Vidpovidna optimizacijna zadacha zadacha pro minimalnu styaguvalnu gusenicyu ZMSG v yakij zadani cini na rebrah i metoyu ye poshuk gusenici yaka minimizuye cini Tut cina gusenici viznachayetsya yak suma cin yiyi reber a kozhne rebro maye dvi cini v zalezhnosti vid togo ye vono listkom chi vnutrishnim rebrom Ne isnuye f n aproksimacijnogo algoritmu dlya ZMSG yaksho ne vikonuyetsya P NP Tut f n bud yaka funkciya vid n sho obchislyuyetsya za polinomialnij chas a n chislo vershin grafu Isnuye parametrizovanij algoritm yakij znahodit optimalnij rozv yazok ZMSG u grafi z obmezhenoyu shirinoyu dereva Takim chinom zavdannya pro styaguvalnu gusenicyu tak i zadacha pro minimalnu styaguvalnu gusenicyu mayut algoritmi linijnogo chasu yaksho graf zovniplanarnij ye paralelno poslidovnim grafom abo grafom Halina ZastosuvannyaGusenici vikoristovuyutsya v himichnij teoriyi grafiv dlya podannya strukturi molekul benzoyidnih vuglevodniv U comu podanni molekuli utvoryuyut gusenici v yakih kozhne rebro vidpovidaye kilcyu z 6 atomiv vuglecyu a dva rebra incidentni vershini yaksho vidpovidni benzolni kilcya nalezhat poslidovnosti spoluchenih linijno kilec angl Sherif El Basil pishe Divno sho majzhe vsi grafi yaki vidigrayut vazhlivu rol u tomu sho zaraz nazivayetsya himichnoyu teoriyeyu grafiv pov yazani z grafami gusenicyami U comu konteksti grafi gusenici vidomi takozh yak benzoyidni dereva abo dereva Gutmana za robotami Ivana Gutmana v cij galuzi Div takozhGraciozna rozmitkaPrimitkiHarary Schwenk 1973 s 359 365 El Basil 1987 s 153 174 Harary Schwenk 1973 Harary Schwenk 1971 s 138 140 Harary Schwenk 1972 s 203 209 Raychaudhuri 1995 s 299 306 Proskurowski Telle 1999 s 167 176 Eckhoff 1993 s 117 127 Weisstein Eric W Lobster angl na sajti Wolfram MathWorld Khosravani 2011 Gutman 1977 s 309 315 El Basil 1990 s 273 289 LiteraturaMasoud Khosravani Searching for optimal caterpillars in general and bounded treewidth graphs Ph D 2011 Sherif El Basil Applications of caterpillar trees in chemistry and physics Journal of Mathematical Chemistry 1987 T 1 vip 2 S 153 174 DOI 10 1007 BF01205666 Ivan Gutman Topological properties of benzenoid systems Theoretica Chimica Acta 1977 T 45 vip 4 S 309 315 DOI 10 1007 BF00554539 Sherif El Basil Advances in the Theory of Benzenoid Hydrocarbons 1990 T 153 S 273 289 DOI 10 1007 3 540 51505 4 28 Andrzej Proskurowski Jan Arne Telle Classes of graphs with restricted interval models Discrete Mathematics and Theoretical Computer Science 1999 T 3 S 167 176 Arundhati Raychaudhuri The total interval number of a tree and the Hamiltonian completion number of its line graph Information Processing Letters 1995 T 56 vip 6 S 299 306 DOI 10 1016 0020 0190 95 00163 8 Jurgen Eckhoff Extremal interval graphs Journal of Graph Theory 1993 T 17 vip 1 S 117 127 DOI 10 1002 jgt 3190170112 Frank Harary Allen J Schwenk Trees with Hamiltonian square Mathematika 1971 T 18 S 138 140 DOI 10 1112 S0025579300008494 Frank Harary Allen J Schwenk A new crossing number for bipartite graphs Utilitas Math 1972 T 1 S 203 209 Frank Harary Allen J Schwenk The number of caterpillars Discrete Mathematics 1973 T 6 vip 4 S 359 365 DOI 10 1016 0012 365x 73 90067 8 PosilannyaWeisstein Eric W Caterpillar angl na sajti Wolfram MathWorld

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