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

У теорії графів граф метелик а також краватка метелик або пісковий годинник це планарний неорієнтований граф з 5 вершина

Метелик (теорія графів)

Метелик (теорія графів)

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

Граф «Метелик»
image
(Вершин) 5
(Ребер) 6
(Радіус) 1
(Діаметр) 2
(Обхват) 3
(Автоморфізм) 8 (D4)
Хроматичне число 3
Хроматичний індекс 4
Властивості планарний
граф одиничних відстаней
ейлерів
не мають граціозної розмітки

Метелик має (діаметр) 2 і обхват 3, радіус 1, хроматичне число 3, хроматичний індекс 4 і є як ейлеровим, так і графом одиничних відстаней. Граф є вершинно 1-зв'яним і реберно 2-зв'язним.

Існує тільки 3 простих графів з п'ятьма вершинами, що не мають граціозної розмітки. Один з них — метелик. Два інших — цикл C5 і повний граф K5.

Графи, що не містять метеликів

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

У вершинно k-зв'язному графі ребро називають k-стягувальним, якщо стягування ребра призводить до k-зв'язного графу. Андо, Канеко, Каварабаяші і Йошімото довели, що будь-який вершинно k-зв'язний граф без метеликів має k-стягувальне ребро.

Алгебричні властивості

Повна група автоморфізмів графу-метелика є групою порядку 8, ізоморфною D4, групі симетрії квадрата, включно з обертанням і відображенням.

Характеристичним многочленом матриці графу-метелика є image.

Див. також

Примітки

  1. Weisstein, Eric W. Butterfly Graph(англ.) на сайті Wolfram MathWorld.
  2. ISGCI: Information System on Graph Classes and their Inclusions. «List of Small Graphs [ 22 липня 2012 у Wayback Machine.]».
  3. Weisstein, Eric W. Graceful graph(англ.) на сайті Wolfram MathWorld.
  4. Ando, 2007, с. 10–20.

Література

  • Kiyoshi Ando. Discrete geometry, combinatorics and graph theory. — Springer, Berlin, 2007. — Т. 4381. — С. 10–20. — (Lecture Notes in Comput. Sci.) — DOI:10.1007/978-3-540-70666-3_2.

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

U teoriyi grafiv graf metelik a takozh kravatka metelik abo piskovij godinnik ce planarnij neoriyentovanij graf z 5 vershinami i 6 rebrami Graf mozhna pobuduvati ob yednannyam dvoh kopij cikliv C3 za odniyeyu spilnoyu vershinoyu a tomu graf izomorfnij grafu tovarishuvannya F2 Graf Metelik Vershin 5Reber 6Radius 1Diametr 2Obhvat 3Avtomorfizm 8 D4 Hromatichne chislo 3Hromatichnij indeks 4Vlastivosti planarnij graf odinichnih vidstanej ejleriv ne mayut gracioznoyi rozmitki Metelik maye diametr 2 i obhvat 3 radius 1 hromatichne chislo 3 hromatichnij indeks 4 i ye yak ejlerovim tak i grafom odinichnih vidstanej Graf ye vershinno 1 zv yanim i reberno 2 zv yaznim Isnuye tilki 3 prostih grafiv z p yatma vershinami sho ne mayut gracioznoyi rozmitki Odin z nih metelik Dva inshih cikl C5 i povnij graf K5 Grafi sho ne mistyat metelikivGraf ye vilnim vid metelikiv yaksho vin ne maye metelika porodzhenim pidgrafom Grafi bez trikutnikiv ye grafami bez metelikiv oskilki graf metelik mistit trikutniki U vershinno k zv yaznomu grafi rebro nazivayut k styaguvalnim yaksho styaguvannya rebra prizvodit do k zv yaznogo grafu Ando Kaneko Kavarabayashi i Joshimoto doveli sho bud yakij vershinno k zv yaznij graf bez metelikiv maye k styaguvalne rebro Algebrichni vlastivostiPovna grupa avtomorfizmiv grafu metelika ye grupoyu poryadku 8 izomorfnoyu D4 grupi simetriyi kvadrata vklyuchno z obertannyam i vidobrazhennyam Harakteristichnim mnogochlenom matrici grafu metelika ye x 1 x 1 2 x 2 x 4 displaystyle x 1 x 1 2 x 2 x 4 Div takozhGolova bika teoriya grafiv PrimitkiWeisstein Eric W Butterfly Graph angl na sajti Wolfram MathWorld ISGCI Information System on Graph Classes and their Inclusions List of Small Graphs 22 lipnya 2012 u Wayback Machine Weisstein Eric W Graceful graph angl na sajti Wolfram MathWorld Ando 2007 s 10 20 LiteraturaKiyoshi Ando Discrete geometry combinatorics and graph theory Springer Berlin 2007 T 4381 S 10 20 Lecture Notes in Comput Sci DOI 10 1007 978 3 540 70666 3 2

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