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

У теорії графів k дерево це неорієнтований граф який утворюється з k 1 вершинного повного графа до якого послідовно дода

K-дерево

K-дерево

У теорії графів k-дерево — це неорієнтований граф, який утворюється з (k + 1)-вершинного повного графа, до якого послідовно додаються вершини таким чином, що кожна додана вершина v має точно k сусідів U таких, що разом k + 1 вершин, утворених з v і U, утворюють кліку.

image
Граф Голднера — Харарі є прикладом планарного 3-дерева.

Характеристики

K-дерева — це в точності максимальні графи зі заданою деревною шириною, графи, до яких не можна додати більше ребер без збільшення ширини їхніх дерев. Вони також є хордальними графами, всі максимальні кліки яких мають однаковий розмір k + 1 і всі мінімальні клікові сепаратори також мають однаковий розмір k.

Будь-яке k-дерево однозначно розфарбовується в (k + 1) колір. Однозначно розфарбовуються в 4 кольори планарні графи — це точно графи Аполлонія, тобто планарні 3-дерева.

Зв'язні класи графів

1-дерева — це то саме, що і некореневі дерева. 2-дерева — це максимальні послідовно-паралельні графи, і вони включають також максимальні зовніпланарні графи. Планарні 3-дерева є також відомі як графи Аполлонія.

Графи, що мають ширину дерева не більшу, ніж k, є в точності підграфами k-дерева, і з цієї причини їх називають частковими k-деревами.

Графи, утворені ребрами і вершинами k-вимірних блокових многогранників, які у свою чергу утворені починаючи з симплекса, потім послідовно симплекси приклеєні на грані многогранника, є k-деревами, якщо k ≥ 3. Цей процес склеювання імітує побудову k-дерев, додаючи вершини до кліки. k-дерево є графом блокового многогранника тоді і тільки тоді, коли ніякі три кліки з (k + 1)-вершинами не мають k спільних вершин.

Посилання

  1. Patil, H. P. (1986), On the structure of k-trees, Journal of Combinatorics, Information and System Sciences, 11 (2-4): 57—64, MR 0966069
  2. ; (2008), (PDF), у (ред.), Building Bridges: between Mathematics and Computer Science, Bolyai Society Mathematical Studies, т. 19, Springer-Verlag, с. 390, ISBN , архів оригіналу (PDF) за 22 липня 2018, процитовано 23 червня 2019.
  3. Thomas Fowler. Unique Coloring of Planar Graphs. — Georgia Institute of Technology Mathematics Department, 1998. — (Ph.D. thesis)
  4. Hwang, Frank; Richards, Dana; Winter, Pawel (1992), The Steiner Tree Problem, Annals of Discrete Mathematics (North-Holland Mathematics Studies), т. 53, Elsevier, с. 177, ISBN .
  5. Distances in random Apollonian network structures [ 21 липня 2011 у Wayback Machine.], talk slides by Olivier Bodini, Alexis Darrasse, and Michèle Soria from a talk at FPSAC 2008, accessed 2011-03-06.
  6. Koch, Etan; (1976), Covering efficiency of trees and k-trees, Proceedings of the Seventh Southeastern Conference on Combinatorics, Graph Theory, and Computing (Louisiana State Univ., Baton Rouge, La., 1976), Utilitas Math., Winnipeg, Man., с. 391–420. Congressus Numerantium, No. XVII, MR 0457265. Див. стор. 420.
  7. Alexander Below, Jesús A. De Loera, Jürgen Richter-Gebert. The Complexity of Finding Small Triangulations of Convex 3-Polytopes.
  8. Kleinschmidt, Peter (1 грудня 1976). Eine graphentheoretische Kennzeichnung der Stapelpolytope. Archiv der Mathematik. 27 (1): 663—667. doi:10.1007/BF01224736.

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

U teoriyi grafiv k derevo ce neoriyentovanij graf yakij utvoryuyetsya z k 1 vershinnogo povnogo grafa do yakogo poslidovno dodayutsya vershini takim chinom sho kozhna dodana vershina v maye tochno k susidiv U takih sho razom k 1 vershin utvorenih z v i U utvoryuyut kliku Graf Goldnera Harari ye prikladom planarnogo 3 dereva HarakteristikiK dereva ce v tochnosti maksimalni grafi zi zadanoyu derevnoyu shirinoyu grafi do yakih ne mozhna dodati bilshe reber bez zbilshennya shirini yihnih derev Voni takozh ye hordalnimi grafami vsi maksimalni kliki yakih mayut odnakovij rozmir k 1 i vsi minimalni klikovi separatori takozh mayut odnakovij rozmir k Bud yake k derevo odnoznachno rozfarbovuyetsya v k 1 kolir Odnoznachno rozfarbovuyutsya v 4 kolori planarni grafi ce tochno grafi Apolloniya tobto planarni 3 dereva Zv yazni klasi grafiv1 dereva ce to same sho i nekorenevi dereva 2 dereva ce maksimalni poslidovno paralelni grafi i voni vklyuchayut takozh maksimalni zovniplanarni grafi Planarni 3 dereva ye takozh vidomi yak grafi Apolloniya Grafi sho mayut shirinu dereva ne bilshu nizh k ye v tochnosti pidgrafami k dereva i z ciyeyi prichini yih nazivayut chastkovimi k derevami Grafi utvoreni rebrami i vershinami k vimirnih blokovih mnogogrannikiv yaki u svoyu chergu utvoreni pochinayuchi z simpleksa potim poslidovno simpleksi prikleyeni na grani mnogogrannika ye k derevami yaksho k 3 Cej proces skleyuvannya imituye pobudovu k derev dodayuchi vershini do kliki k derevo ye grafom blokovogo mnogogrannika todi i tilki todi koli niyaki tri kliki z k 1 vershinami ne mayut k spilnih vershin PosilannyaPatil H P 1986 On the structure of k trees Journal of Combinatorics Information and System Sciences 11 2 4 57 64 MR 0966069 2008 PDF u red Building Bridges between Mathematics and Computer Science Bolyai Society Mathematical Studies t 19 Springer Verlag s 390 ISBN 978 3 540 85218 6 arhiv originalu PDF za 22 lipnya 2018 procitovano 23 chervnya 2019 Thomas Fowler Unique Coloring of Planar Graphs Georgia Institute of Technology Mathematics Department 1998 Ph D thesis Hwang Frank Richards Dana Winter Pawel 1992 The Steiner Tree Problem Annals of Discrete Mathematics North Holland Mathematics Studies t 53 Elsevier s 177 ISBN 978 0 444 89098 6 Distances in random Apollonian network structures 21 lipnya 2011 u Wayback Machine talk slides by Olivier Bodini Alexis Darrasse and Michele Soria from a talk at FPSAC 2008 accessed 2011 03 06 Koch Etan 1976 Covering efficiency of trees and k trees Proceedings of the Seventh Southeastern Conference on Combinatorics Graph Theory and Computing Louisiana State Univ Baton Rouge La 1976 Utilitas Math Winnipeg Man s 391 420 Congressus Numerantium No XVII MR 0457265 Div stor 420 Alexander Below Jesus A De Loera Jurgen Richter Gebert The Complexity of Finding Small Triangulations of Convex 3 Polytopes Kleinschmidt Peter 1 grudnya 1976 Eine graphentheoretische Kennzeichnung der Stapelpolytope Archiv der Mathematik 27 1 663 667 doi 10 1007 BF01224736

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