Тороїдальний граф

Кубічний граф з 14 вершинами, вкладений в тор

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

Приклади

Будь-який граф, який можна вкласти у площину, також можна вкласти у тор. Тороїдальний будь-який граф із числом схрещень 1, наприклад: граф Хівуда, повний граф (і як наслідок, та ), граф Петерсена, один зі снарків Блануші[1] та всі драбини Мебіуса. Деякі графи з великим числом схрещень також є тороїдальними, наприклад, граф Мебіуса — Кантора, який має число схрещень 4[2].

Властивості

Хроматичне число будь-якого тороїдального графа не перевищує 7[3]; прикладом тороїдального графа з хроматичним числом 7 є повний граф [4]. Хроматичне число будь-якого тороїдального графа без трикутників не перевищує 4[5].

Аналогічно теоремі Фарі, будь-який тороїдальний граф можна побудувати з ребрами у вигляді відрізків у прямокутнику з періодичними межами (тобто протилежні границі квадрата ототожнюються)[6]. Крім того, у цьому випадку може бути застосована теорема Татта[7].

Тороїдальні графи також допускають книжкове вкладення з максимум 7 листами[8].

Див. також

Примітки

  1. ↑ Orbanić et al., 2004.
  2. ↑ Marušič & Pisanski, 2000.
  3. ↑ Heawood, 1890.
  4. ↑ Chartrand & Zhang, 2008.
  5. ↑ Kronk & White, 1972.
  6. ↑ Kocay, Neilson, Szypowski, 2001.
  7. ↑ Gortler, Gotsman, Thurston, 2006.
  8. ↑ Endo, 1997.

Література

  • Chartrand, Gary; Zhang, Ping (2008), Chromatic graph theory, CRC Press, ISBN 978-1-58488-800-0.
  • Endo, Toshiki (1997), The pagenumber of toroidal graphs is at most seven, Discrete Mathematics, 175 (1–3): 87—96, doi:10.1016/S0012-365X(96)00144-6, MR 1475841.
  • Gortler, Steven J.; Gotsman, Craig; Thurston, Dylan (2006), Discrete one-forms on meshes and applications to 3D mesh parameterization, Computer Aided Geometric Design, 23 (2): 83—112, doi:10.1016/j.cagd.2005.05.002, MR 2189438.
  • Heawood, P. J. (1890), Map colouring theorems, Quarterly J. Math. Oxford Ser., 24: 322—339.
  • Kocay, W.; Neilson, D.; Szypowski, R. (2001), Drawing graphs on the torus (PDF), Ars Combinatoria, 59: 259—277, MR 1832459, архів оригіналу (PDF) за 24 грудня 2004, процитовано 9 травня 2019.
  • Kronk, Hudson V.; White, Arthur T. (1972), A 4-color theorem for toroidal graphs, Proceedings of the American Mathematical Society, American Mathematical Society, 34 (1): 83—86, doi:10.2307/2037902, JSTOR 2037902, MR 0291019.
  • Marušič, Dragan; Pisanski, Tomaž (2000), The remarkable generalized Petersen graph G(8,3), Math. Slovaca, 50: 117—121[недоступне посилання з травня 2019].
  • Neufeld, Eugene; Myrvold, Wendy (1997), Practical toroidality testing, Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, с. 574—580.
  • Orbanić, Alen; Pisanski, Tomaž; Randić, Milan; Servatius, Brigitte (2004), Blanuša double, Math. Commun., 9 (1): 91—103.

Read other articles:

Direktorat Jenderal Bimbingan Masyarakat Kristen

Direktorat Jenderal Bimbingan Masyarakat Kristen Kementerian Agama Republik IndonesiaSusunan organisasiDirektur JenderalDr. Jeane Marie Tulung, S.Th., M.Pd.Sekretaris DitjenJohni Tilaar, S.Th., M.Si.Direktur Urusan Agama KristenDr. Amsal Yowei, S.E., M.Pd.K.Direktur Pendidikan Agama KristenDrs. Sudirman Simanihuruk, M.Th. Kantor pusatKantor Kementerian Agama RI lt. 10-11, Jalan M. H. Thamrin No. 6, Jakarta 10340Situs webbimaskristen.kemenag.go.id Direktorat Jenderal Bimbingan Masyarakat ...

 

I Don't See Me in Your Eyes Anymore

1949 popular song This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: I Don't See Me in Your Eyes Anymore – news · newspapers · books · scholar · JSTOR (August 2011) (Learn how and when to remove this template message) I Don't See Me in Your Eyes AnymoreSingle by Charlie Richfrom the album There Won't Be Anymore...

 

Athletic Club 2010-2011

Voce principale: Athletic Club. Questa voce sull'argomento stagioni delle società calcistiche spagnole è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Athletic ClubStagione 2010-2011I giocatori prima dell'amichevole con il Lens Sport calcio Squadra Athletic Bilbao Allenatore Joaquín Caparrós Presidente Fernando García Macua Primera División6º posto (in Europa League) Coppa del ReOttavi di finale Miglior marcatoreCampionato: Llorente (18) 20...

Women in Black

Women's anti-war movement Not to be confused with The Woman in Black. Women in Black staging a protest in New Paltz, New York Women in Black (Hebrew: נשים בשחור, romanized: Nashim BeShahor) is a women's anti-war movement with an estimated 10,000 activists around the world. The first group was formed by Israeli women in Jerusalem in 1988, following the outbreak of the First Intifada.[1] History This section needs additional citations for verification. Please help improve ...

 

Charles Spaak

Questa voce o sezione sull'argomento sceneggiatori non cita le fonti necessarie o quelle presenti sono insufficienti. Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti. Segui i suggerimenti del progetto di riferimento. Charles Spaak Charles Spaak (Saint-Gilles, 25 maggio 1903 – Nizza, 4 marzo 1975) è stato uno sceneggiatore belga. Biografia Sia il padre che la madre erano politici belgi. Il padre, Paul, era avvocato e d...

 

Battlefield Play4Free

This article needs to be updated. Please help update this article to reflect recent events or newly available information. (March 2012) 2011 video gameBattlefield Play4FreeDeveloper(s)Easy StudiosPublisher(s)Electronic ArtsDesigner(s)Colin ClarkeSeriesBattlefieldPlatform(s)Microsoft WindowsRelease4 April 2011 (open beta)[1]Genre(s)First-person shooterMode(s)Multiplayer Battlefield Play4Free is a defunct first-person shooter video game developed by Easy Studios and published by Electr...

Tea production in the United States

Camellia sinensis, the source of tea leaves and buds, can be grown in much of the United States. Commercial cultivation has been tried at various times and locations since the 1700s, but tea has remained a niche crop and has never been cultivated widely in the US. As of 2020, the US mainland has one relatively large plantation with full mechanization in Charleston, South Carolina, and many small commercial tea gardens that pick tea by hand. Some growers feel that tea production is not economi...

 

Gender expression

This article is written like a research paper or scientific journal. Please help improve the article by rewriting it in encyclopedic style and simplify overly technical phrases. (December 2022) (Learn how and when to remove this message) Part of a series onTransgender topics      OutlineHistoryTimeline Gender identities Androgyne Bissu, Calabai, Calalai Burrnesha Cisgender Gender bender Hijra Non-binary or genderqueer Gender fluidity Kathoey Koekchuch Third gender Ba...

 

List of deans and notable people at the NYU Grossman School of Medicine

This list includes deans, notable alumni and faculty of NYU Grossman School of Medicine. List of deans The NYU Langone Orthopedic Hospital on Second Avenue at East 17th Street John W. Draper, President of the Faculty (1850–1873) Alfred C. Post, President of the Faculty (1873–1877) Charles Inslee Pardee, Dean (1877–1897) Egbert Le Fevre, Acting Dean (1897–1898) Edward G. Janeway, Dean (1898–1905) Egbert Le Fevre, Dean (1905–1914) William H. Park, Acting Dean (1914–1915) Samuel A...

Bandar Udara Namlea

Namniwel AirportBandar Udara NamniwelIATA: NAMICAO: WAPRInformasiJenisPublicPemilikPemerintah IndonesiaPengelolaKementerian Perhubungan Republik IndonesiaMelayaniNamleaLokasiNamlea, Pulau Buru, Maluku, IndonesiaZona waktuWIT (UTC+09:00)Ketinggian dpl12 mdplKoordinat003°14′13″S 127°06′01″E / 3.23694°S 127.10028°E / -3.23694; 127.10028Koordinat: 003°14′13″S 127°06′01″E / 3.23694°S 127.10028°E / -3.23694; 127.10028...

 

GR-113808

Chemical compound GR-113808Identifiers IUPAC name 1-(2-methylsulfonylaminoethyl-4-piperidinyl)methyl-1-methyl-1H-indole-3-carboxylate CAS Number144625-51-4PubChem CID119376IUPHAR/BPS247ChemSpider106623UNIIZT350OYT3ICompTox Dashboard (EPA)DTXSID40162772 Chemical and physical dataFormulaC19H27N3O4SMolar mass393.50 g·mol−13D model (JSmol)Interactive image SMILES c13ccccc3c(cn1C)C(=O)OCC(CC2)CCN2CCNS(=O)(C)=O InChI InChI=1S/C19H27N3O4S/c1-21-13-17(16-5-3-4-6-18(16)21)19(23)26-14-15-7-10-2...

 

شهر العسل في فيجاس

شهر العسل في فيجاسHoneymoon in Vegas (بالإنجليزية) معلومات عامةالصنف الفني كوميديالموضوع قمار تاريخ الصدور 1992مدة العرض 92 دقيقةاللغة الأصلية الإنجليزيةالبلد الولايات المتحدةموقع التصوير لاس فيغاس فالي الطاقمالمخرج أندرو بيرغمان[1][2][3] السيناريو أندرو بيرغمان البطول...

Sirius (mythology)

Stellar god in Greek mythology This article is about the Greek god. For the star, see Sirius. For other uses, see Sirius (disambiguation). SiriusGod of the star SiriusCanis Major and Lepus with Sirius as the dog's snout, as depicted in Urania's Mirror, a set of constellation cards c. 1825.GreekΣείριοςAbodeSkyPersonal informationParentsAstraeus (possibly) (father)Eos (possibly) (mother)Siblingsthe StarsConsortOpora In Greek and Roman mythology, Sirius[a] is the god and personifi...

 

New York State Route 123

State highway in Westchester County, New York, US New York State Route 123Smith Ridge RoadMap of Westchester County in southeastern New York with NY 123 highlighted in redRoute informationMaintained by NYSDOTLength4.68 mi[1] (7.53 km)Existed1930[2]–presentMajor junctionsSouth end Route 123 in New Canaan, CTNorth end NY 35 in South Salem LocationCountryUnited StatesStateNew YorkCountiesWestchester Highway system New York Highways Inters...

 

Pino III Ordelaffi

Pino III OrdelaffiPino III Ordelaffi(Busto di Francesco di Simone Ferrucci, Pinacoteca comunale di Forlì)Signore di ForlìStemma In carica1466 –1480 PredecessoreFrancesco IV Ordelaffi SuccessoreSinibaldo II Ordelaffi NascitaForlì, 11 marzo 1436 MorteForlì, 10 febbraio 1480 (43 anni) Luogo di sepolturaChiesa di San Biagio DinastiaOrdelaffi PadreAntonio Ordelaffi MadreCaterina Rangoni ConiugiBarbara ManfrediZaffira ManfrediLucrezia Pico della Mirandola FigliSinibaldo II (na...

Hashimoto, Wakayama

Hashimoto 橋本市Kota BenderaLambangLokasi Hashimoto di Prefektur WakayamaNegara JepangWilayahKansaiPrefektur WakayamaPemerintahan • Wali kotaTetsurō HirakiLuas • Total131 km2 (51 sq mi)Populasi (Oktober 1, 2015) • Total63.621 • Kepadatan485,7/km2 (1,258/sq mi)Zona waktuUTC+09:00Kode pos648-8585Simbol  • PohonOsmanthus fragransPrunus serrulata • BungaRhododendron indicumNomor...

 

Cathédrale Notre-Dame de Dax

Pour les articles homonymes, voir Cathédrale Notre-Dame et Notre-Dame. CathédraleNotre-Dame de Dax Présentation Culte Catholique romain Dédicataire Vierge Marie Type Cathédrale Rattachement Diocèse d'Aire et Dax (siège) Début de la construction XIIIe siècle Fin des travaux XVIIIe siècle Style dominant classiqueGothique (Portail des Apôtres) Protection  Classée MH (1946) Site web Paroisse Saint-Paul-Saint-Vincent-de-Dax Géographie Pays France Région Nouvelle-...

 

Kuala Pembuang (kota)

Kuala Pembuang كوالا فمبواڠIbukota kabupatenKuala Pembuang selama karnaval yang diadakan untuk memperingati HUT-RI ke-79, 18 Agustus 2024.Kuala PembuangLokasi Kuala PembuangTampilkan peta Kalimantan TengahKuala PembuangKuala Pembuang (Kalimantan)Tampilkan peta KalimantanKuala PembuangKuala Pembuang (Indonesia)Tampilkan peta IndonesiaKoordinat: 3°23′14″S 112°32′36″E / 3.3871°S 112.5434°E / -3.3871; 112.5434Negara IndonesiaProvinsiKalimantan T...

班

班（はん） 集団を何人かずつ、小分けにした小集団。例：研究班、捜査班、取材班 軍隊の部隊単位の一つ。本項にて解説。 陸軍の部隊単位   常設編制 総軍 地域軍 戦域軍 軍集団 方面軍 戦線 軍（方面隊） 軍団 師団 旅団 連隊 半旅団（准旅団） 団 群 大隊 中隊 小隊 分隊 班 組 常設諸兵科連合編制 旅団戦闘団 即応機動連隊 大隊戦術群 臨時編成 コンバット・コマ�...

 

2000 State of Origin series

Australian rugby league series 2000 State of Origin seriesWon by New South Wales (9th title)Series margin3-0Points scored146Attendance159,074 (ave. 53,025 per match)Top points scorer(s) Ryan Girdler (52)Top try scorer(s) Ryan Girdler (5) ← 1999 State of Origin series 2001 → The 2000 State of Origin series was the 19th year that the annual three-game series between the Queensland and New South Wales representative rugby league football teams was played entirely under 'state of origin'...