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

У теорії графів зірка Sk англ star це повний двочастковий граф K1 k дерево з єдиним внутрішнім вузлом і k листками але п

Зірка (теорія графів)

Зірка (теорія графів)

У теорії графів зірка Sk (англ. star) — це повний двочастковий граф K1,k: дерево з єдиним внутрішнім вузлом і k листками (але при k ≤ 1 має k+1 листків і не має внутрішніх вузлів). Крім того, деякі автори визначають Sk як дерево порядку k з максимальною відстанню 2; в цьому випадку зірка k > 2 має k − 1 листок.

Зірка
image
ЗіркаS7. (Деякі автори позначають як S8.)
(Вершин) k+1
(Ребер) k
(Діаметр) minimum of (2, k)
(Обхват) ∞
Хроматичне число minimum of (2,k+1)
Хроматичний індекс k
1
Властивості Реберно-транзитивний граф
Дерево
Граф одиничних відстаней
Двочастковий
Позначення Sk

Зірка з 3-ма ребрами називається клешнею.

Зірка Sk називається [en], коли k парне і не є такою, коли непарне. Вона є реберно-транзитивною сірниковому графу, і має відстань 2 (при k>1), обхват ∞ (не має циклів), хроматичний індекс k і хроматичне число 2 (при k> 0). Крім того, зірка має велику групу автоморфізмів, а саме симетричну групу з k букв.

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

Зв'язок з іншими типами графів

Клешні зустрічаються у визначенні графів без клешень, графів, які не мають підграфів з клешнями. Крім того, вони є одним з виняткових випадків теореми ізоморфізму графів Вітні: загалом, графи з ізоморфними реберними графами так само є ізоморфними, за винятком клешень і трикутника K3.

Зірка є особливим видом дерева. Як і будь-яке дерево, зірки можуть бути закодовані за допомогою коду Прюфера; послідовність Прюфера для зірки K1,k складається з k-1 копії центральної вершини.

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

image
Зірки S3, S4, S5 та S6.

Інші застосування

Множина відстаней між вершинами клешні є прикладом кінцевого метричного простору, який не можна ізометрично вкласти в евклідів простір будь-якої розмірності.

Топологія «Зірка», комп'ютерна мережа змодельована на основі графа-зірки, відіграє важливу роль у розподілених обчисленнях.

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

Матричне представлення

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

Єдиний внутрішній вузол — перша вершина Єдиний внутрішній вузол — остання вершина

Джерела

  1. Faudree, Ralph; Flandrin, Evelyne; Ryjáček, Zdeněk (10 лютого 1997). . Discrete Mathematics. Т. 164, № 1–3. с. 87—147. doi:10.1016/S0012-365X(96)00045-3. Архів оригіналу за 16 березня 2022. Процитовано 27 березня 2016.
  2. Chudnovsky, Maria; Seymour, Paul (2005). "The structure of claw-free graphs" (English) . London Math. Soc. Lecture Note Ser. 327: Cambridge: Cambridge Univ. Press. с. 153—171. MR 2187738.
  3. Whitney, Hassler (1 січня 1932). . American Journal of Mathematics. Т. 54, № 1. с. 150—168. doi:10.2307/2371086. Архів оригіналу за 8 квітня 2016. Процитовано 27 березня 2016.
  4. Gottlieb, J.; Julstrom, B. A.; Rothlauf, F.; Raidl, G. R. (2001). "Prüfer numbers: A poor representation of spanning trees for evolutionary search" (English) . Morgan Kaufmann. с. 343—350.
  5. Hakimi, S. L.; Mitchem, J.; Schmeichel, E. (22 лютого 1996). . Discrete Mathematics. Т. 149, № 1–3. с. 93—98. doi:10.1016/0012-365X(94)00313-8. Архів оригіналу за 6 травня 2021. Процитовано 27 березня 2016.
  6. Fertin, Guillaume; Raspaud, André; Reed, Bruce (1 листопада 2004). . Journal of Graph Theory (англ.). Т. 47, № 3. с. 163—182. doi:10.1002/jgt.20029. ISSN 1097-0118. Архів оригіналу за 3 травня 2016. Процитовано 27 березня 2016.
  7. Robertson, Neil; Seymour, P. D (1 липня 1991). . Journal of Combinatorial Theory, Series B. Т. 52, № 2. с. 153—190. doi:10.1016/0095-8956(91)90061-N. Архів оригіналу за 6 травня 2021. Процитовано 27 березня 2016.
  8. Linial, Nathan (2002). "Finite metric spaces–combinatorics, geometry and algorithms" (English) . Proc. International Congress of Mathematicians, Beijing 3. с. 573—586.

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

U teoriyi grafiv zirka Sk angl star ce povnij dvochastkovij graf K1 k derevo z yedinim vnutrishnim vuzlom i k listkami ale pri k 1 maye k 1 listkiv i ne maye vnutrishnih vuzliv Krim togo deyaki avtori viznachayut Sk yak derevo poryadku k z maksimalnoyu vidstannyu 2 v comu vipadku zirka k gt 2 maye k 1 listok ZirkaZirkaS7 Deyaki avtori poznachayut yak S8 Vershin k 1Reber kDiametr minimum of 2 k Obhvat Hromatichne chislo minimum of 2 k 1 Hromatichnij indeks k1Vlastivosti Reberno tranzitivnij graf Derevo Graf odinichnih vidstanej DvochastkovijPoznachennya Sk Zirka z 3 ma rebrami nazivayetsya kleshneyu Zirka Sk nazivayetsya en koli k parne i ne ye takoyu koli neparne Vona ye reberno tranzitivnoyu sirnikovomu grafu i maye vidstan 2 pri k gt 1 obhvat ne maye cikliv hromatichnij indeks k i hromatichne chislo 2 pri k gt 0 Krim togo zirka maye veliku grupu avtomorfizmiv a same simetrichnu grupu z k bukv Zirka takozh mozhe buti opisana yak zv yaznij graf v yakomu ne bilshe odniyeyi vershini sho maye stepin bilshe odinici Zv yazok z inshimi tipami grafivKleshni zustrichayutsya u viznachenni grafiv bez kleshen grafiv yaki ne mayut pidgrafiv z kleshnyami Krim togo voni ye odnim z vinyatkovih vipadkiv teoremi izomorfizmu grafiv Vitni zagalom grafi z izomorfnimi rebernimi grafami tak samo ye izomorfnimi za vinyatkom kleshen i trikutnika K3 Zirka ye osoblivim vidom dereva Yak i bud yake derevo zirki mozhut buti zakodovani za dopomogoyu kodu Pryufera poslidovnist Pryufera dlya zirki K1 k skladayetsya z k 1 kopiyi centralnoyi vershini Dekilka invariantiv grafiv viznacheni v terminah zirok Arborichnist ce minimalna kilkist lisiv yaki mozhe utvoriti graf takim chinom sho kozhne derevo v kozhnomu lisi ye zirkoyu en nazivayetsya minimalne chislo koloriv neobhidnih dlya farbuvannya jogo vershin takim chinom shob kozhni dva klasi koloriv razom utvoryuvali pidgraf u yakomu vsi z yednani komponenti ye zirkami Grafi z shirinoyu gilok 1 ye same takimi grafami de kozhna z yednana komponenta ye zirkoyu Zirki S3 S4 S5 ta S6 Inshi zastosuvannyaMnozhina vidstanej mizh vershinami kleshni ye prikladom kincevogo metrichnogo prostoru yakij ne mozhna izometrichno vklasti v evklidiv prostir bud yakoyi rozmirnosti Topologiya Zirka komp yuterna merezha zmodelovana na osnovi grafa zirki vidigraye vazhlivu rol u rozpodilenih obchislennyah Geometrichna realizaciya grafa zirki formuyetsya shlyahom viznachennya reber z intervalami deyakoyi fiksovanoyi dovzhini vikoristovuyetsya yak lokalna model krivih u tropichnij geometriyi Tropichna kriva viznachayetsya yak metrichnij prostir sho lokalno izomorfnij yak metrichnij graf zirchastoyi formi Matrichne predstavlennyaZa pevnoyi numeraciyi matrichne podannya grafa zirki mozhe mati formu strili Zauvazhte yak proste perenumeruvannya vershin grafa mozhe vplinuti na shvidkodiyu algoritmiv U vipadku metodu Gausa vikoristannya matrici iz zapovnenim verhnim ryadkom prizvede do zgubnogo dlya shvidkodiyi algoritmu zapovnennya nulovih komirok Yedinij vnutrishnij vuzol persha vershina Yedinij vnutrishnij vuzol ostannya vershinaDzherelaFaudree Ralph Flandrin Evelyne Ryjacek Zdenek 10 lyutogo 1997 Discrete Mathematics T 164 1 3 s 87 147 doi 10 1016 S0012 365X 96 00045 3 Arhiv originalu za 16 bereznya 2022 Procitovano 27 bereznya 2016 Chudnovsky Maria Seymour Paul 2005 The structure of claw free graphs English London Math Soc Lecture Note Ser 327 Cambridge Cambridge Univ Press s 153 171 MR 2187738 Whitney Hassler 1 sichnya 1932 American Journal of Mathematics T 54 1 s 150 168 doi 10 2307 2371086 Arhiv originalu za 8 kvitnya 2016 Procitovano 27 bereznya 2016 Gottlieb J Julstrom B A Rothlauf F Raidl G R 2001 Prufer numbers A poor representation of spanning trees for evolutionary search English Morgan Kaufmann s 343 350 Hakimi S L Mitchem J Schmeichel E 22 lyutogo 1996 Discrete Mathematics T 149 1 3 s 93 98 doi 10 1016 0012 365X 94 00313 8 Arhiv originalu za 6 travnya 2021 Procitovano 27 bereznya 2016 Fertin Guillaume Raspaud Andre Reed Bruce 1 listopada 2004 Journal of Graph Theory angl T 47 3 s 163 182 doi 10 1002 jgt 20029 ISSN 1097 0118 Arhiv originalu za 3 travnya 2016 Procitovano 27 bereznya 2016 Robertson Neil Seymour P D 1 lipnya 1991 Journal of Combinatorial Theory Series B T 52 2 s 153 190 doi 10 1016 0095 8956 91 90061 N Arhiv originalu za 6 travnya 2021 Procitovano 27 bereznya 2016 Linial Nathan 2002 Finite metric spaces combinatorics geometry and algorithms English Proc International Congress of Mathematicians Beijing 3 s 573 586

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