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

Універсальна вершина це вершина неорієнтованого графа яка суміжна всім іншим вершинам графа Вона може також називатися д

Універсальна вершина

Універсальна вершина

Універсальна вершина — це вершина неорієнтованого графа, яка суміжна всім іншим вершинам графа. Вона може також називатися домінівною вершиною, оскільки вона утворює одноелементну домінівну множину в графі.

Граф, який містить універсальну вершину, можна також назвати конусом. У цьому контексті універсальну вершину називають апексом конуса, однак це конфліктує з термінологією верхівкових графів, в яких іноді апексом називають вершину, видалення якої робить граф планарним.

У спеціальних сімействах графів

Зірки — це дерева, які мають універсальну вершину і можуть бути побудовані шляхом додавання універсальної вершини в незалежну множину. Колеса, аналогічно, можна утворити шляхом додавання універсальної вершини в цикл. У геометрії тривимірні піраміди мають колеса як кістяки, а більш загальні графи будь-якої піраміди в просторі будь-якої розмірності мають універсальну вершину як вершину (апекс) піраміди.

Тривіально досконалі графи (графи порівнянності ) завжди містять універсальну вершину, а саме, корінь дерева, і можуть бути описані як графи, в яких будь-який породжений підграф містить універсальну вершину. Досконалі порогові графи утворюють підклас тривіально досконалих графів, так що вони містять універсальну вершину. Їх можна визначити як графи, які можна утворити шляхом повторюваного додавання або універсальної вершини, або ізольованої вершини (тобто вершини без ребер).

Будь-який граф з універсальною вершиною і майже всі розбиранні графи мають універсальну вершину.

Інші властивості

У графі з n вершинами універсальна вершина — це вершина, степінь якої в дорівнює n − 1. Тому, подібно до , графи з універсальною вершиною можна розпізнати чисто за їхньою послідовністю степенів без перегляду структури графів.

Див. також

Примітки

  1. Larrión, de Mello, Morgana, Neumann-Lara, Pizaña, 2004, с. 183–191.
  2. Bonato, 2008, с. 7.
  3. Wolk, 1962, с. 789–795.
  4. Chvátal, Hammer, 1977, с. 145–162.
  5. Bonato, Kemkes, Prałat, 2012, с. 1652–1657.

Література

  • Larrión F., de Mello C. P., Morgana A., Neumann-Lara V., Pizaña M. A. The clique operator on cographs and serial graphs // Discrete Mathematics. — 2004. — Т. 282, вип. 1-3. — С. 183–191. — DOI:10.1016/j.disc.2003.10.023.
  • Anthony Bonato. A course on the web graph. — Atlantic Association for Research in the Mathematical Sciences (AARMS), Halifax, NS, 2008. — Т. 89. — С. 7. — (Graduate Studies in Mathematics) — . — DOI:10.1090/gsm/089.
  • Wolk E. S. The comparability graph of a tree // Proceedings of the American Mathematical Society. — 1962. — Т. 13. — С. 789–795. — DOI:10.2307/2034179.
  • Václav Chvátal, Peter Ladislaw Hammer. Aggregation of inequalities in integer programming // Studies in Integer Programming (Proc. Worksh. Bonn 1975) / Hammer P. L., Johnson E. L., Korte B. H., Nemhauser G. L. — Amsterdam : North-Holland, 1977. — Т. 1. — С. 145–162. — (Annals of Discrete Mathematics)
  • Anthony Bonato, Graeme Kemkes, Paweł Prałat. Almost all cop-win graphs contain a universal vertex // . — 2012. — Т. 312, вип. 10. — С. 1652–1657. — DOI:10.1016/j.disc.2012.02.018.

Посилання

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

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

Universalna vershina ce vershina neoriyentovanogo grafa yaka sumizhna vsim inshim vershinam grafa Vona mozhe takozh nazivatisya dominivnoyu vershinoyu oskilki vona utvoryuye odnoelementnu dominivnu mnozhinu v grafi Graf yakij mistit universalnu vershinu mozhna takozh nazvati konusom U comu konteksti universalnu vershinu nazivayut apeksom konusa odnak ce konfliktuye z terminologiyeyu verhivkovih grafiv v yakih inodi apeksom nazivayut vershinu vidalennya yakoyi robit graf planarnim U specialnih simejstvah grafivZirki ce dereva yaki mayut universalnu vershinu i mozhut buti pobudovani shlyahom dodavannya universalnoyi vershini v nezalezhnu mnozhinu Kolesa analogichno mozhna utvoriti shlyahom dodavannya universalnoyi vershini v cikl U geometriyi trivimirni piramidi mayut kolesa yak kistyaki a bilsh zagalni grafi bud yakoyi piramidi v prostori bud yakoyi rozmirnosti mayut universalnu vershinu yak vershinu apeks piramidi Trivialno doskonali grafi grafi porivnyannosti zavzhdi mistyat universalnu vershinu a same korin dereva i mozhut buti opisani yak grafi v yakih bud yakij porodzhenij pidgraf mistit universalnu vershinu Doskonali porogovi grafi utvoryuyut pidklas trivialno doskonalih grafiv tak sho voni mistyat universalnu vershinu Yih mozhna viznachiti yak grafi yaki mozhna utvoriti shlyahom povtoryuvanogo dodavannya abo universalnoyi vershini abo izolovanoyi vershini tobto vershini bez reber Bud yakij graf z universalnoyu vershinoyu i majzhe vsi rozbiranni grafi mayut universalnu vershinu Inshi vlastivostiU grafi z n vershinami universalna vershina ce vershina stepin yakoyi v dorivnyuye n 1 Tomu podibno do grafi z universalnoyu vershinoyu mozhna rozpiznati chisto za yihnoyu poslidovnistyu stepeniv bez pereglyadu strukturi grafiv Div takozhUniversalnij grafPrimitkiLarrion de Mello Morgana Neumann Lara Pizana 2004 s 183 191 Bonato 2008 s 7 Wolk 1962 s 789 795 Chvatal Hammer 1977 s 145 162 Bonato Kemkes Pralat 2012 s 1652 1657 LiteraturaLarrion F de Mello C P Morgana A Neumann Lara V Pizana M A The clique operator on cographs and serial graphs Discrete Mathematics 2004 T 282 vip 1 3 S 183 191 DOI 10 1016 j disc 2003 10 023 Anthony Bonato A course on the web graph Atlantic Association for Research in the Mathematical Sciences AARMS Halifax NS 2008 T 89 S 7 Graduate Studies in Mathematics ISBN 978 0 8218 4467 0 DOI 10 1090 gsm 089 Wolk E S The comparability graph of a tree Proceedings of the American Mathematical Society 1962 T 13 S 789 795 DOI 10 2307 2034179 Vaclav Chvatal Peter Ladislaw Hammer Aggregation of inequalities in integer programming Studies in Integer Programming Proc Worksh Bonn 1975 Hammer P L Johnson E L Korte B H Nemhauser G L Amsterdam North Holland 1977 T 1 S 145 162 Annals of Discrete Mathematics Anthony Bonato Graeme Kemkes Pawel Pralat Almost all cop win graphs contain a universal vertex 2012 T 312 vip 10 S 1652 1657 DOI 10 1016 j disc 2012 02 018 PosilannyaWeisstein Eric W Cone Graph angl na sajti Wolfram MathWorld

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