Алмаз (теорія графів)

Алмаз
Вершин4
Ребер5
Радіус1
Діаметр2
Обхват3
Автоморфізм4 (Z/2Z×Z/2Z)
Дробово-хроматичне число3
Дробово-хроматичний індекс3
ВластивостіГраф одиничних відстаней
Планарний
Гамільтонів

Алмаз — це планарний неорієнтований граф із 4 вершинами та 5 ребрами[1][2]. Граф являє собою повний граф без одного ребра.

Радіус алмаза дорівнює 1, діаметр дорівнює 2, обхват дорівнює 3, хроматичний індекс і хроматичне число дорівнюють 3. Граф також вершинно 2-зв'язаний і реберно 2-зв'язаний, має граціозну розмітку[3] і є гамільтоновим.

Графи без алмазів і заборонені мінори

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

Сімейство графів, в якому кожна зв'язна компонента є кактусом, замкнуто донизу відносно операції утворення мінору графа. Це сімейство графів може бути описано єдиним забороненим мінором — алмазом[4].

Якщо метелик й алмаз є забороненими мінорами, отримане сімейство графів є сімейством псевдолісів.

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

Група автоморфізмів алмаза є групою порядку 4, ізоморфною четверній групі Клейна, прямому добутку циклічної групи Z/2Z на себе.

Характеристичний многочлен алмаза дорівнює . Алмаз є єдиним графом із характеристичним многочленом, що визначає граф за його спектром.

Примітки

  1. ↑ Weisstein, Eric W. Diamond Graph(англ.) на сайті Wolfram MathWorld.
  2. ↑ ISGCI: Information System on Graph Classes and their Inclusions "List of Small Graphs [Архівовано 22 липня 2012 у Wayback Machine.]".
  3. ↑ Sin-Min Lee, Y.C. Pan and Ming-Chen Tsai. "On Vertex-graceful (p,p+l)-Graphs". Архівована копія (PDF). Архів оригіналу (PDF) за 7 серпня 2008. Процитовано 16 вересня 2009.{{cite web}}: Обслуговування CS1: Сторінки з текстом «archived copy» як значення параметру title (посилання) [Архівовано 2008-08-07 у Wayback Machine.]
  4. ↑ El-Mallah, Colbourn, 1988, с. 354–362.

Література

  • Ehab El-Mallah, Charles J. Colbourn. The complexity of some edge deletion problems // IEEE Transactions on Circuits and Systems. — 1988. — Т. 35, вип. 3. — С. 354–362. — DOI:10.1109/31.1748.

Read other articles:

Bad Housewife

2005 South Korean comedy-drama TV series Bad HousewifeAlso known asHouse HusbandHangul불량주부Hanja不良主婦Revised RomanizationBullyang jubuMcCune–ReischauerPullyang jubu GenreComedy dramaFamily dramaScreenplay byEun-jung Kang Junseok SeolDirected byYoo In-sik Jang Tae-yuStarringSon Chang-min Shin Ae-ra Yuko FuekiCountry of originSouth KoreaNo. of episodes18ProductionProducersYoo In-shik Jang Tae-yooRunning time70 minutesProduction companyCK MediaworksOriginal releaseNetworkSeoul Br...

 

General Nakar, Quezon

Peta menunjukkan lokasi General Nakar General Nakar adalah munisipalitas yang terletak di provinsi Quezon, Filipina. Pada tahun 2010, munisipalitas ini memiliki populasi sebesar 25.395 jiwa dan 4.997 rumah tangga. Pembagian wilayah Secara administratif General Nakar terbagi menjadi 19 barangay, yaitu: Anoling Banglos Batangan Catablingan Canaway Lumutan Mahabang Lalim Maigang Maligaya Magsikap Minahan Norte Minahan Sur Pagsangahan Pamplona Pesa Poblacion Sablang San Marcelino Umiray Pranala l...

 

Thomas Dudley

Governor of Massachusetts Bay Colony (1576–1653) For other people named Thomas Dudley, see Thomas Dudley (disambiguation). Thomas Dudley3rd, 7th, 11th, and 14th Governor of the Massachusetts Bay ColonyIn office1634–1635Preceded byJohn WinthropSucceeded byJohn HaynesIn office1640–1641Preceded byJohn WinthropSucceeded byRichard BellinghamIn office1645–1646Preceded byJohn EndecottSucceeded byJohn WinthropIn office1650–1651Preceded byJohn EndecottSucceeded byJohn EndecottCommissione...

Deuterokanonika

Bagian dari Alkitab KristenPerjanjian LamaYosua 1:1 pada Kodeks Aleppo Taurat Kejadian Keluaran Imamat Bilangan Ulangan Sejarah Yosua Hakim-hakim Rut 1 Samuel 2 Samuel 1 Raja-raja 2 Raja-raja 1 Tawarikh 2 Tawarikh Ezra Nehemia Ester Puisi Ayub Mazmur Amsal Pengkhotbah Kidung Agung Kenabian Besar Yesaya Yeremia Ratapan Yehezkiel Daniel Kecil Hosea Yoël Amos Obaja Yunus Mikha Nahum Habakuk Zefanya Hagai Zakharia Maleakhi Deuterokanonika Tobit Yudit Tambahan Ester 1 Makabe 2 Makabe Kebijaksanaa...

 

Pongchon County

This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages) You can help expand this article with text translated from the corresponding article in Polish. (October 2022) Click [show] for important translation instructions. Consider adding a topic to this template: there are already 1,449 articles in the main category, and specifying|topic= will aid in categorization. Do not translate t...

 

Richard Wagner

Disambiguazione – Se stai cercando altri significati, vedi Richard Wagner (disambigua). Disambiguazione – Wagner rimanda qui. Se stai cercando altri significati, vedi Wagner (disambigua). Richard Wagner fotografato nel 1871 Wilhelm Richard Wagner[1] (in italiano pronunciato /ˈvaɡner/[2]; in tedesco ['vɪlhɛlm 'ʀɪçaʀt 'va:gnɐ]; Lipsia, 22 maggio 1813 – Venezia, 13 febbraio 1883) è stato un compositore, poeta, regista teatrale, direttore d'orchestra e sag...

Avenida Presidente Masaryk

Street in Mexico City Avenida Presidente MasarykNamesakeTomáš MasarykLocationPolanco, Miguel HidalgoMexico City, MexicoNearest metro stationPolancoEastCalzada General Mariano EscobedoWestAvenida Ferrocarril de Cuernavaca Avenida Presidente Masaryk is a thoroughfare in the affluent Polanco neighborhood of Mexico City. It stretches from Calzada General Mariano Escobedo in the east to Avenida Ferrocarril de Cuernavaca in the west, passing along the north side of the Polanquito restaurant distr...

 

约翰斯顿环礁

此條目可参照英語維基百科相應條目来扩充。 (2021年5月6日)若您熟悉来源语言和主题，请协助参考外语维基百科扩充条目。请勿直接提交机械翻译，也不要翻译不可靠、低品质内容。依版权协议，译文需在编辑摘要注明来源，或于讨论页顶部标记{{Translated page}}标签。 约翰斯顿环礁Kalama Atoll 美國本土外小島嶼 Johnston Atoll 旗幟颂歌：《星條旗》The Star-Spangled Banner約翰斯頓環礁�...

 

Новотитаровское сельское поселение

Сельское поселение России (МО 2-го уровня)Новотитаровское сельское поселение Флаг[d] Герб 45°14′09″ с. ш. 38°58′16″ в. д.HGЯO Страна  Россия Субъект РФ Краснодарский край Район Динской Включает 4 населённых пункта Адм. центр Новотитаровская Глава сельского пос�...

Parandra cribrata

Artikel ini sebatang kara, artinya tidak ada artikel lain yang memiliki pranala balik ke halaman ini.Bantulah menambah pranala ke artikel ini dari artikel yang berhubungan atau coba peralatan pencari pranala.Tag ini diberikan pada Desember 2022. Parandra cribrata Klasifikasi ilmiah Kerajaan: Animalia Filum: Arthropoda Kelas: Insecta Ordo: Coleoptera Famili: Cerambycidae Genus: Parandra Spesies: Parandra cribrata Parandra cribrata adalah spesies kumbang tanduk panjang yang tergolong famili Cer...

 

كثافة

كثافة الكتليةمعلومات عامةالرموز الشائعة ρ Dالتعريف الرياضي ρ = d m d V {\displaystyle \rho ={\frac {\mathrm {d} m}{\mathrm {d} V}}} [1][2][3]نظام الوحدات الدولي كجم/م3التحليل البعدي L − 3 M {\displaystyle {\mathsf {L}}^{-3}{\mathsf {M}}} تعديل - تعديل مصدري - تعديل ويكي بيانات برج الكثافة, ويوضح بعض المواد المختل...

 

Welsh folk music

Overview of folk music in Wales Part of a series on theCulture of Wales History Timeline Bibliography Prehistory Roman Era Anglo-Welsh Wars Early Middle Ages Kingdom of Gwynedd Kingdom of Powys Deheubarth Medieval Welsh law Norman invasion Edwardian conquest Late Middle Ages Statute of Rhuddlan Glyndŵr rebellion Laws in Wales Acts 1535 and 1542 Colonies People Languages Welsh (Y Fro Gymraeg History Welsh placenames Welsh surnames Welsh-medium education) Welsh English Welsh Romani Traditions ...

Serbia en el Festival de la Canción de Eurovisión

Serbia Estación miembro Final Nacional Beovizija Apariciones 17 (2024) Primera aparición 2007 Mejor resultado Final 1º 2007 Semifinal 1º 2007 Peor resultado Final 24° 2023 Semifinal 11º 2013, 2017 Enlaces externos Página en PTC Página de Serbia en Eurovision.tv Serbia participa en el Festival de la Canción de Eurovisión como país independiente desde 2007. Previamente, Serbia apareció en el Festival de la Canción de Eurovisión como parte de la República Socialista de Yugoslavia...

 

The Departed

2006 American crime thriller film by Martin Scorsese This article is about the 2006 film. For other uses, see The Departed (disambiguation). The DepartedTheatrical release posterDirected byMartin ScorseseScreenplay byWilliam MonahanBased onInfernal Affairsby Alan Mak & Felix ChongProduced by Brad Pitt Brad Grey Graham King Starring Leonardo DiCaprio Matt Damon Jack Nicholson Mark Wahlberg Martin Sheen Ray Winstone Vera Farmiga Alec Baldwin CinematographyMichael BallhausEdited byThelma Sch...

 

Kuwait

Dieser Artikel befasst sich mit dem Staat Kuwait. Zur Hauptstadt Kuwaits siehe Kuwait (Stadt). Staat Kuwait arabisch دولة الكويت Daulat al-Kuwait Flagge Wappen Amtssprache Arabisch Hauptstadt Kuwait Staats- und Regierungsform Konstitutionelle Monarchie Staatsoberhaupt EmirMischal al-Ahmad al-Dschabir as-Sabah Regierungschef PremierministerScheich Ahmad al-Abdullah as-Sabah Fläche 17.818 km² Einwohnerzahl 4,3 Millionen (126.) (2020; Schätzung)[1] Bevölkerungsdichte 2...

Grand Prix E3 2015

Grand Prix E3 2015 Zdeněk Štybar ({{2e}}), Geraint Thomas ({{1er}}) et Matteo Trentin ({{3e}}).GénéralitésCourse58e E3 Saxo Bank ClassicCompétitionUCI World Tour 2015 1.UWTDate27 mars 2015Distance215 kmPays BelgiqueLieu de départHarelbekeLieu d'arrivéeHarelbekeÉquipes24Partants190Arrivants126Vitesse moyenne40,952 km/hSite officielSite officielRésultatsVainqueur Geraint Thomas (Team Sky)Deuxième Zdeněk Štybar (Etixx-Quick Step)Troisième Matteo Trentin (Etixx-Quick Step) ◀2...

 

Mula (Murcia)

Mula municipio de EspañaBanderaEscudo Vista de Mula y su vega. MulaUbicación de Mula en España MulaUbicación de Mula en la Región de Murcia País  España• Com. autónoma  Región de Murcia• Provincia  Murcia• Comarca Comarca del Río Mula• Partido judicial MulaUbicación 38°02′31″N 1°29′26″O / 38.0418669, -1.4906872• Altitud 313 m(mín:?, máx: 1521)Superficie 633,38 ...

 

C-SPAN

この記事は英語版の対応するページを翻訳することにより充実させることができます。（2022年2月）翻訳前に重要な指示を読むには右にある[表示]をクリックしてください。 英語版記事を日本語へ機械翻訳したバージョン（Google翻訳）。 万が一翻訳の手がかりとして機械翻訳を用いた場合、翻訳者は必ず翻訳元原文を参照して機械翻訳の誤りを訂正し、正確な翻訳にし�...

Mayotte Capécia

Martiniquan writer (1916–1955) Mayotte CapéciaMayotte Capécia (right) with writer and literary critic Léo LarguierBornLucette Céranus(1916-02-17)February 17, 1916Le Carbet, MartiniqueDiedNovember 24, 1955(1955-11-24) (aged 39)Paris, FranceOccupationAuthorNotable workI Am a Martinican Woman Lucette Céranus Combette (17 February 1916 – 24 November 1955), known by her pen name Mayotte Capécia was a writer from Martinique. She is best known for her novel I Am a Martinican Woman (Fr...

 

Emmit King

Questa voce sull'argomento atleti statunitensi è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Segui i suggerimenti del progetto di riferimento. Emmit KingNazionalità Stati Uniti Atletica leggera SpecialitàVelocità Record 50 m 562 (indoor - 1986) 60 m 655 (indoor - 1988) 100 m 1004 (1988) 200 m 2086 (1982) CarrieraSocietà Alabama Crimson Tide Nazionale 1979-1983 Stati Uniti Palmarès Competizione Ori Argenti Bronzi Mondial...