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

Алмаз

Вершин	4
Рёбер	5
Радиус	1
Диаметр	2
Обхват	3
Автоморфизмы	4 (Z/2Z×Z/2Z)
Хроматическое число	3
Хроматический индекс	3
Свойства	Граф единичных расстояний планарный Гамильтонов
Медиафайлы на Викискладе

Алмаз — планарный неориентированный граф с 4 вершинами и 5 рёбрами^[1]^[2]. Граф представляет собой полный граф $K_{4}$ без одного ребра.

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

Графы без алмазов и запрещённые миноры

Граф является свободным от алмазов, если он не содержит алмаза в качестве порождённого подграфа. Графы без треугольников являются свободными от алмазов, поскольку любой алмаз содержит треугольник.

Семейство графов, в котором каждая связная компонента является кактусом, замкнуто вниз относительно операции образования минора графа. Это семейство графов может быть описано единственным запрещённым минором — алмазом^[4].

Если бабочка и алмаз являются запрещёнными минорами, полученное семейство графов является семейством псевдолесов.

Алгебраические свойства

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

Характеристический многочлен алмаза равен $x(x+1)(x^{2}-x-4)$ . Алмаз является единственным графом с характеристическим многочленом, определяющим граф его спектром.

См. также

Матроид Вамоса^[англ.]

Примечания

↑ Weisstein, Eric W. Diamond Graph (англ.) на сайте Wolfram MathWorld.
↑ ISGCI: Information System on Graph Classes and their Inclusions "List of Small Graphs Архивировано 18 ноября 2012 года.".
↑ Sin-Min Lee, Y.C. Pan and Ming-Chen Tsai. "On Vertex-graceful (p,p+l)-Graphs". Архивированная копия (неопр.). Дата обращения: 16 сентября 2009. Архивировано 7 августа 2008 года.
↑ 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:

Iglesia de Nuestra Señora de la Asunción (Cabañas de la Sagra)

Iglesia de Nuestra Señora de la Asunción LocalizaciónPaís España EspañaComunidad Castilla-La Mancha Castilla-La ManchaProvincia Toledo ToledoLocalidad Cabañas de la SagraUbicación Cabañas de la SagraCoordenadas 40°00′25″N 3°56′48″O / 40.006877777778, -3.946625Información religiosaCulto catolicismo[editar datos en Wikidata] La iglesia de Nuestra Señora de la Asunción es una iglesia parroquial católica de los siglos XV y XVI situad...

Sasak (konstruksi)

Artikel ini tidak memiliki referensi atau sumber tepercaya sehingga isinya tidak bisa dipastikan. Tolong bantu perbaiki artikel ini dengan menambahkan referensi yang layak. Tulisan tanpa sumber dapat dipertanyakan dan dihapus sewaktu-waktu.Cari sumber: Sasak konstruksi – berita · surat kabar · buku · cendekiawan · JSTOR Pagar sasak di museum luar ruangan di Polandia Sasak dibuat dengan menenun cabang-cabang fleksibel di sekitar tiang tegak untuk m...

Viceammiraglio della Real Marina delle Due Sicilie

Viceammiraglio della Real Marina delle Due Sicilie Stato Regno delle Due Sicilie Organizzazione Real Marina delle Due Sicilie TipoComandante generale della marina militare Istituito1818 Soppresso1861 SedeNapoli Modifica dati su Wikidata · Manuale Il Viceammiraglio della Real Marina del Regno delle Due Sicilie era il titolo assunto dal comandante generale o supremo del corpo della Real Marina delle Due Sicilie, anche detta Real Armata. Nel tempo il titolo fu riservato ad un familiar...

1912 Boston Red Sox season

Major League Baseball season Major League Baseball team season 1912 Boston Red SoxWorld Series ChampionsAmerican League ChampionsLeagueAmerican LeagueBallparkFenway ParkCityBoston, MassachusettsRecord105–47 (.691)League place1stOwnersJohn I. TaylorJimmy McAleerManagersJake StahlStatsESPN.comBB-reference ← 1911 Seasons 1913 → The 1912 Boston Red Sox season was the 12th season in the franchise's Major League Baseball history. This was the first year that the team pl...

Norbert Meier

German footballer and manager Norbert Meier Meier in 2011Personal informationDate of birth (1958-09-20) 20 September 1958 (age 65)Place of birth Reinbek, West GermanyHeight 1.73 m (5 ft 8 in)Position(s) MidfielderSenior career*Years Team Apps (Gls)1980–1989 Werder Bremen 281 (82)1990–1992 Borussia Mönchengladbach 50 (2)Total 331 (84)International career1981–1982 West Germany B 3 (0)1982–1985 West Germany 16 (2)Managerial career1997–1998 Borussia Mönchengladbach...

Dissuasion et prolifération nucléaires pendant la guerre froide

Dissuasion et prolifération nucléaires pendant la guerre froide Le 16 juillet 1945, l'essai atomique Trinity est la première explosion nucléaire jamais réalisée[1]. Chronologie des années 1945-1959 août 1945 Bombardements atomiques d'Hiroshima et de Nagasaki[2] 15 février 1946 Émergence du concept de dissuasion nucléaire[3] 29 août 1949 URSS : première explosion d'une bombe A[2] 14 avril 1950 États-Unis : adoption d'une posture de supériorité stratégique nucléaire...

Kota Madiun

Halaman ini berisi artikel tentang Kota. Untuk Kabupaten bernama sama, lihat Kabupaten Madiun. Untuk Kegunaan lain, lihat Madiun (disambiguasi). Kota MadiunKotaTranskripsi bahasa daerah • Hanacarakaꦩꦝꦶꦪꦸꦤ꧀ • Pegonمادييون • Alfabet JawaMadhiyunDari atas, kiri ke kanan: Gedung Balai Kota Madiun, Tugu Pendekar, dan Bangunan di kawasan Bosbow LambangJulukan: Kota GadisKota BremKota PecelKota SastraKota BudayaKota IndustriKota Pela...

Piala FA 2019–2020

Piala FA 2019–2020Negara Inggris Guernsey WalesTanggal penyelenggaraan10 Agustus 2019 hingga1 Agustus 2020Jumlah peserta735 (keseluruhan)644 (babak kualifikasi)123 (kompetisi utama)Juara bertahanManchester CityJuaraArsenal (gelar ke-14)Tempat keduaChelseaJumlah pertandingan156Jumlah gol429 (2.75 per pertandingan)Pencetak gol terbanyakJames BallHarry McKirdy(5 gol)← 2018–2019 2020–2021 → Seluruh statistik akurat per 2 Agustus 2020. Piala FA 2019–2020 adalah edisi ke-...

Centers for Medicare & Medicaid Services

United States federal agency This article needs to be updated. Please help update this article to reflect recent events or newly available information. (February 2020) Centers for Medicare & Medicaid ServicesAgency overviewFormedMarch 1977; 47 years ago (1977-03)PrecedingHealth Care Financing Administration (1977-2001)HeadquartersWoodlawn, Baltimore County, Maryland, U.S.Employees6,000Agency executivesChiquita Brooks-LaSure, AdministratorJonathan Blum, Principal Dep...

Hari Chand Dewan

Indian Air Force officer (1921–2017) Air MarshalH C DewanPVSMBorn20 September 1921Died22 August 2017Allegiance British India (1942–1947) India (from 1947)Service/branch Royal Indian Air Force Indian Air ForceBattles/warsBurma Campaign Lt Gen A A K Niazi signing the Pakistani Instrument of Surrender under the gaze of Lt Gen J S Aurora. Standing immediately behind (L-R) Vice Admiral Krishnan, Air Marshal Dewan, Lt. Gen Sagat Singh, Maj Gen JFR Jacob. Air Marshal Hari Cha...

约翰斯顿环礁

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

U.S. Green Building Council

Non-profit organization that promotes sustainability in building design U.S. Green Building Council (USGBC)Formation1993Typenon-profitHeadquartersPhiladelphia (certification and credentialing) and Washington, D.C. (membership, products, and merchandising), U.S.Membership 6,500Key peopleRick FedrizziDavid GottfriedMike ItalianoPeter TempletonWebsitewww.usgbc.org The U.S. Green Building Council (USGBC), founded in 1993, is a private 501(c)3, membership-based non-profit organization that promote...

Oeschinen Lake

Lake in the Bernese Oberland, SwitzerlandOeschinen LakeOeschinen Lake from Heuberg. View towards the Blüemlisalp and the Doldenhorn.Oeschinen LakeShow map of Canton of BernOeschinen LakeShow map of Canton of ValaisOeschinen LakeShow map of SwitzerlandOeschinen LakeShow map of AlpsLocationKandersteg, Bernese OberlandCoordinates46°29′54″N 07°43′37″E / 46.49833°N 7.72694°E / 46.49833; 7.72694Typeoligotrophic, holomicticPrimary inflowsBärglibach, Wyssbach, L�...

Avery Dulles

Yang UtamaAvery Robert Dulles, S.J.Kardinal-Diakon SS. Nomi di Gesù e MariaPenunjukan21 Februari 2001Masa jabatan berakhir12 Desember 2008ImamatTahbisan imam16 Juni 1956Pelantikan kardinal21 Februari 2001Informasi pribadiLahir(1918-08-24)24 Agustus 1918Auburn, New York, Amerika SerikatWafat12 Desember 2008(2008-12-12) (umur 90)Bronx, New York, Amerika SerikatMakamJesuit Cemetery, Auriesville, New York, Amerika SerikatKewarganegaraanAmerika SerikatDenominasiKatolikOrang tuaJohn Foster Du...

André Grétry

André Grétry Nama dalam bahasa asli(fr) André Ernest Modeste Grétry BiografiKelahiran(fr) André-Ernest-Modeste Grétry 8 Februari 1741 Liège Kematian24 September 1813 (72 tahun)Montmorency Tempat pemakamanPemakaman Père-Lachaise, 11 Galat: Kedua parameter tahun harus terisi! Data pribadiPendidikanFondation Lambert-Darchis (1761–1766) KegiatanPekerjaankomponis, penulis GenreOpera dan Opéra comique AliranMusik klasik Murid dariHenri Moreau, Giovanni Battista Casali dan Giovann...

Pavo de Nochebuena

Este artículo o sección necesita referencias que aparezcan en una publicación acreditada. Busca fuentes: «Pavo de Nochebuena» – noticias · libros · académico · imágenesEste aviso fue puesto el 13 de diciembre de 2017. Pavo de Nochebuena Pavo de Nochebuena Pavo asado Tipo Cena (variable)ConsumoOrigen DesconocidoDatos generalesSimilares Turducken[editar datos en Wikidata] El pavo de Nochebuena se come tradicionalmente durante el transcurso de la festivi...

Cage

Enclosure used to confine, contain or protect something or someone For other uses, see Cage (disambiguation). You can help expand this article with text translated from the corresponding article in German. (October 2017) Click [show] for important translation instructions. Machine translation, like DeepL or Google Translate, is a useful starting point for translations, but translators must revise errors as necessary and confirm that the translation is accurate, rather than simply copy-pa...

الدوري الإسكتلندي الدرجة الأولى 2016–17

الدوري الإسكتلندي الدرجة الأولى 2016–17 تفاصيل الموسم البطولة الإسكتلندية النسخة 111 البلد المملكة المتحدة التاريخ بداية:6 أغسطس 2016 نهاية:29 أبريل 2017 المنظم الدوري الإسكتلندي للمحترفين لكرة القدم البطل نادي هيبرنيان مباريات ملعوبة 180 عدد المشاركين ...

كتائب سنغالية

كتائب سنغاليةمعلومات عامةصنف فرعي من فرع عسكري البداية 1857 سُمِّي باسم السنغال البلد فرنسا لديه جزء أو أجزاء Tirailleur (en) تعديل - تعديل مصدري - تعديل ويكي بيانات الكتائب السنغالية (بالفرنسية: Tirailleurs Sénégalais، نقحرة: التيغايوغ السنغالي) كانت كتائب من المُشاة السنغاليين المجندين في...

斯科特體育

斯科特體育Scott Sports公司類型股份公司成立1958年，66年前（1958）（前稱：斯科特美國）創辦人埃德·斯科特總部瑞士吉維謝产业單車、滑雪用品產品滑雪頭盔、滑雪護目鏡网站scott-sports.com 斯科特體育（英語：Scott Sports SA），前稱：斯科特美國（Scott USA），總部設於瑞士吉維謝的體育用品生產商[1]。歷史斯科特S50公路車斯科特滑雪杖 1958年，美國愛達�...

PROFILPELAJAR.COM