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

У теорії графів вітряк Wd k n це неорієнтований граф побудований для k 2 і n 2 об єднанням n копій повних графів Kk в од

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

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

У теорії графів «вітряк» Wd(k,n) — це неорієнтований граф, побудований для k ≥ 2 і n ≥ 2 об'єднанням n копій повних графів Kk в одній спільній вершині. Тобто це сума за 1-клікою цих повних графів.

Властивості

Граф має (k−1)n+1 вершин і nk(k−1)/2 ребер, обхват 3 (при k > 2), радіус 1 і діаметр 2. Граф має вершинну зв'язність 1, оскільки його центральна вершина є точкою зчленування. Однак, подібно до повних графів, з яких він утворений, він є реберно (k-1)-зв'язним. Граф є тривіально досконалим графом і блоковим графом.

Особливі випадки

За побудовою вітряк Wd (3,n) є графом товаришування Fn, вітряк Wd(2,n) є зіркою Sn, а вітряк Wd(3,2) є «метеликом».

Розмітка і розфарбування

Граф «вітряк» має хроматичне число k і хроматичний індекс n(k-1). Його хроматичний многочлен можна отримати з хроматичного многочлена повного графа і він дорівнює image

Доведено, що граф «вітряк» Wd(k,n) не є граціозним, якщо k > 5. 1979 року Бермонд висловив гіпотезу, що Wd(4,n) є граціозним для всіх n ≥ 4. Відомо, що це так для n ≤ 22. Бермонд, Котціг і Тургеон довели, що Wd(k,n) не є граціозними при k = 4 і n = 2 або n = 3, і при k = 5 і n = 2. Вітряк Wd(3,n) граціозний тоді і тільки тоді, коли n ≡ 0 (mod 4) або n ≡ 1 (mod 4).

Галерея

image
Малі графи-вітряки.

Примітка

  1. Gallian, 2007, с. 1-58.
  2. Koh, Rogers, Teo, Yap, 1980, с. 559-571.
  3. Bermond, 1979, с. 18-37.
  4. Huang, Skiena, 1994, с. 225-242.
  5. Bermond, Kotzig, Turgeon, 1978, с. 135-149.
  6. Bermond, Brouwer, Germa, 1978, с. 35-38.

Література

  • J. A. Gallian. Dynamic Survey DS6: Graph Labeling // Electronic J. Combinatorics. — 2007. — Вип. DS6 (3 січня). з джерела 31 січня 2012. Процитовано 29 липня 2021.
  • K. M. Koh, D. G. Rogers, H. K. Teo, K. Y. Yap. Graceful graphs: some further results and problems // Congr. Numer.. — 1980. — Вип. 29 (21 червня).
  • J.C. Bermond. Graph Theory and Combinatorics. — London : Pitman, 1979. — Т. 34. — (Research Notes in Mathematics)
  • J. Huang, S. Skiena. Gracefully labeling prisms // Ars Combinatoria. — 1994. — Вип. 38 (21 червня).
  • J. C. Bermond, A. Kotzig, J. Turgeon. Proc. 18 Hungarian Combinatorial Colloquium, Keszthely (1976) / A. Hajnal and V. T. Sos, eds. — North-Holland, Amsterdam, 1978. — (Colloquia mathematica Societatis János Bolyai)
  • J.C. Bermond, A. E. Brouwer, A. Germa. Problèmes Combinatoires et Théorie des Graphes. — Paris : Editions du Centre Nationale de la Recherche Scientifique, 1978. — Т. 260. — (Colloq. Intern. du CNRS)

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

U teoriyi grafiv vitryak Wd k n ce neoriyentovanij graf pobudovanij dlya k 2 i n 2 ob yednannyam n kopij povnih grafiv Kk v odnij spilnij vershini Tobto ce suma za 1 klikoyu cih povnih grafiv VlastivostiGraf maye k 1 n 1 vershin i nk k 1 2 reber obhvat 3 pri k gt 2 radius 1 i diametr 2 Graf maye vershinnu zv yaznist 1 oskilki jogo centralna vershina ye tochkoyu zchlenuvannya Odnak podibno do povnih grafiv z yakih vin utvorenij vin ye reberno k 1 zv yaznim Graf ye trivialno doskonalim grafom i blokovim grafom Osoblivi vipadkiZa pobudovoyu vitryak Wd 3 n ye grafom tovarishuvannya Fn vitryak Wd 2 n ye zirkoyu Sn a vitryak Wd 3 2 ye metelikom Rozmitka i rozfarbuvannyaGraf vitryak maye hromatichne chislo k i hromatichnij indeks n k 1 Jogo hromatichnij mnogochlen mozhna otrimati z hromatichnogo mnogochlena povnogo grafa i vin dorivnyuye i 0 k 1 x i n displaystyle prod i 0 k 1 x i n Dovedeno sho graf vitryak Wd k n ne ye gracioznim yaksho k gt 5 1979 roku Bermond visloviv gipotezu sho Wd 4 n ye gracioznim dlya vsih n 4 Vidomo sho ce tak dlya n 22 Bermond Kotcig i Turgeon doveli sho Wd k n ne ye gracioznimi pri k 4 i n 2 abo n 3 i pri k 5 i n 2 Vitryak Wd 3 n gracioznij todi i tilki todi koli n 0 mod 4 abo n 1 mod 4 GalereyaMali grafi vitryaki PrimitkaGallian 2007 s 1 58 Koh Rogers Teo Yap 1980 s 559 571 Bermond 1979 s 18 37 Huang Skiena 1994 s 225 242 Bermond Kotzig Turgeon 1978 s 135 149 Bermond Brouwer Germa 1978 s 35 38 LiteraturaJ A Gallian Dynamic Survey DS6 Graph Labeling Electronic J Combinatorics 2007 Vip DS6 3 sichnya z dzherela 31 sichnya 2012 Procitovano 29 lipnya 2021 K M Koh D G Rogers H K Teo K Y Yap Graceful graphs some further results and problems Congr Numer 1980 Vip 29 21 chervnya J C Bermond Graph Theory and Combinatorics London Pitman 1979 T 34 Research Notes in Mathematics J Huang S Skiena Gracefully labeling prisms Ars Combinatoria 1994 Vip 38 21 chervnya J C Bermond A Kotzig J Turgeon Proc 18 Hungarian Combinatorial Colloquium Keszthely 1976 A Hajnal and V T Sos eds North Holland Amsterdam 1978 Colloquia mathematica Societatis Janos Bolyai J C Bermond A E Brouwer A Germa Problemes Combinatoires et Theorie des Graphes Paris Editions du Centre Nationale de la Recherche Scientifique 1978 T 260 Colloq Intern du CNRS

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