Клітка (теорія графів): відмінності між версіями
[неперевірена версія] | [перевірена версія] |
м вікіфікація |
вікіфікація, оформлення, доповнення |
||
Рядок 1: | Рядок 1: | ||
{{Значення|Клітка (значення)}} |
{{Значення|Клітка (значення)}} |
||
[[Файл:Petersen1 tiny.svg|thumb|right|Граф Петерсена]] |
[[Файл:Petersen1 tiny.svg|thumb|right|[[Граф Петерсена]]]] |
||
[[Файл:Heawood tiny.svg|thumb|right|Граф |
[[Файл:Heawood tiny.svg|thumb|right|[[Граф Хівуда]]]] |
||
[[Файл:McGee graph.svg|thumb|Граф |
[[Файл:McGee graph.svg|thumb|{{Не перекладено|Граф МакЖі|||McGee graph}}]] |
||
[[Файл:Tutte eight cage.svg|thumb|Граф Татта — Коксетера]] |
[[Файл:Tutte eight cage.svg|thumb|[[Граф Татта — Коксетера]]]] |
||
[[Файл:Hoffman_singleton_graph_circle2.gif|thumb|right|Граф Гофмана-Синглтона]] |
[[Файл:Hoffman_singleton_graph_circle2.gif|thumb|right|{{Не перекладено|Граф Гофмана-Синглтона|||Hoffman–Singleton graph}}]] |
||
'''n-клітка''' |
'''n-клітка''' — кубічний граф обхвату ''n'' з найменшим можливим числом вершин. Граф називається ''кубічним'', якщо з кожної його вершини виходять 3 ребра. [[Обхват (теорія графів)|''Обхват'' графа]] — це довжина найменшого циклу в ньому. |
||
* 3-клітка |
* 3-клітка — '''К<sub>4</sub>''', остов [[тетраедр]]а, 4 вершини. |
||
* 4-клітка |
* 4-клітка — '''К<sub>3,3</sub>''', один з двох мінімальних не [[Планарний граф|планарних]] графів, 6 вершин. |
||
* 5-клітка |
* 5-клітка — [[Граф Петерсена]], 10 вершин. Мінімальний кубічний граф з індексом самоперетину 2. |
||
* 6-клітка |
* 6-клітка — [[Граф Хівуда]], 14 вершин. Розбивається на 1-фактори (тобто, реберно розфарбовуємий), будь-яка сума двох чинників утворює [[гамільтонів цикл]]. Мінімальний кубічний граф з індексом самоперетину 3. |
||
* 7-клітка |
* 7-клітка — {{Не перекладено|Граф МакЖі|||McGee graph}}, 24 вершини. Мінімальний кубічний граф з індексом самоперетину 8. |
||
* 8-клітка |
* 8-клітка — [[Граф Татта — Коксетера]], 30 вершин. |
||
== Узагальнене визначення |
== Узагальнене визначення == |
||
'''(''r'',''n'')-клітка''' |
'''(''r'',''n'')-клітка''' — регулярний граф ступеня ''r'' (тобто з кожної вершини якого виходить рівно ''r'' ребер) та обхвату ''n'' з найменшим можливим числом вершин. |
||
'''Тривіальні сімейства''' |
'''Тривіальні сімейства''' |
||
* (2,''n'')-клітками є, очевидно, циклічні графи '''C<sub>''n''</sub>''' |
* (2,''n'')-клітками є, очевидно, циклічні графи '''C<sub>''n''</sub>''' |
||
* (''r''-1,3)-клітки |
* (''r''-1,3)-клітки — повні графи '''К<sub>''r''</sub>''' з ''r'' вершин |
||
* (''r'',4)-клітки |
* (''r'',4)-клітки — повні дводольні графи '''К<sub>''r'',''r''</sub>''', у яких в кожній долі знаходиться по ''r'' вершин |
||
'''Нетривіальні представники''' |
'''Нетривіальні представники''' |
||
* (7,5)-клітка |
* (7,5)-клітка — Граф Гофмана-Сінглтона, 50 вершин. |
||
Відомі ще деякі клітки. У таблиці нижче показано кількість вершин в (''r'',''n'')-клітинах ступеня 3≤''r''≤7 та обхвату 3≤''n''≤12. Клітки для цих та великих ''r'' и ''n'' описані тут: [http://people.csse.uwa.edu.au/gordon/cages/allcages.html] (англійською мовою). |
Відомі ще деякі клітки. У таблиці нижче показано кількість вершин в (''r'',''n'')-клітинах ступеня 3≤''r''≤7 та обхвату 3≤''n''≤12. Клітки для цих та великих ''r'' и ''n'' описані тут: [http://people.csse.uwa.edu.au/gordon/cages/allcages.html] (англійською мовою). |
||
Рядок 47: | Рядок 47: | ||
: <math>2\sum_{i=0}^{(n-2)/2}(r-1)^i</math> для парних. |
: <math>2\sum_{i=0}^{(n-2)/2}(r-1)^i</math> для парних. |
||
Якщо має місце рівність, то відповідний граф називається '''графом Мура'''. У той час як клітка існує для будь-яких ''r'' > 2 і ''n'' > 2, нетривіальних графів Мура набагато менше. З вищезгаданих клітин, графами Мура є [[Граф Петерсена]], [[граф Хівуда]], [[граф Татта — Коксетера]] і граф Гофмана- |
Якщо має місце рівність, то відповідний граф називається '''графом Мура'''. У той час як клітка існує для будь-яких ''r'' > 2 і ''n'' > 2, нетривіальних графів Мура набагато менше. З вищезгаданих клітин, графами Мура є [[Граф Петерсена]], [[граф Хівуда]], [[граф Татта — Коксетера]] і {{Не перекладено|граф Гофмана-Синглтона|||Hoffman–Singleton graph}}. Доведено,<ref>Bannai, E. and Ito, T. «On Moore Graphs.» J. Fac. Sci. Univ. Tokyo Ser. A 20, 191—208, 1973</ref><ref>Damerell, R. M. «On Moore Graphs.» Proc. Cambridge Philos. Soc. 74, 227—236, 1973</ref><ref>Hoffman, A. J. and Singleton, R. R. «On Moore Graphs of Diameter 2 and 3.» IBM J. Res. Develop. 4, 497—504, 1960</ref> що всі непарні випадки вичерпуються ''n'' = 5, ''r'' = 2, 3, 7 та, можливо, 57, а парні ''n'' = 6, 8, 12. |
||
== Примітки == |
== Примітки == |
||
Рядок 53: | Рядок 53: | ||
== Література == |
== Література == |
||
* Ф. Харари ''Теория графов''. |
* Ф. Харари ''Теория графов''. — М.: [[УРСС]], — 2003. — 300 с — ISBN 5-354-00301-6. |
||
== Посилання == |
== Посилання == |
||
*{{citation |
|||
* {{MathWorld|CageGraph|Клеточный граф}} |
|||
| last = Biggs | first = Norman | authorlink = Norman L. Biggs |
|||
* http://people.csse.uwa.edu.au/gordon/cages/ {{ref-en}} |
|||
| edition = 2nd |
|||
{{math-stub}} |
|||
| isbn = 0-521-45897-8 |
|||
| pages = 180–190 |
|||
| publisher = Cambridge Mathematical Library |
|||
| title = Algebraic Graph Theory |
|||
| year = 1993}}. |
|||
*{{citation |
|||
| last1 = Bollobás | first1 = Béla | author1-link = Béla Bollobás |
|||
| last2 = Szemerédi | first2 = Endre | author2-link = Endre Szemerédi |
|||
| doi = 10.1002/jgt.10023 |
|||
| issue = 3 |
|||
| journal = [[Journal of Graph Theory]] |
|||
| mr = 1883596 |
|||
| pages = 194–200 |
|||
| title = Girth of sparse graphs |
|||
| volume = 39 |
|||
| year = 2002}}. |
|||
*{{citation |
|||
| last1 = Exoo | first1 = G |
|||
| last2 = Jajcay | first2 = R |
|||
| journal = [[Electronic Journal of Combinatorics]] | department = Dynamic Surveys |
|||
| title = Dynamic Cage Survey |
|||
| url = http://www.combinatorics.org/ojs/index.php/eljc/article/download/ds16/pdf |
|||
| volume = DS16 |
|||
| year = 2008}}. |
|||
*{{citation |
|||
| last1 = Erdős | first1 = Paul | author1-link = Paul Erdős |
|||
| last2 = Rényi | first2 = Alfréd | author2-link = Alfréd Rényi |
|||
| last3 = Sós | first3 = Vera T. | author3-link = Vera T. Sós |
|||
| journal = Studia Sci. Math. Hungar. |
|||
| pages = 215–235 |
|||
| title = On a problem of graph theory |
|||
| url = http://www.math-inst.hu/~p_erdos/1966-06.pdf |
|||
| volume = 1 |
|||
| year = 1966}}. |
|||
*{{citation |
|||
| last1 = Hartsfield | first1 = Nora | author1-link = Nora Hartsfield |
|||
| last2 = Ringel | first2 = Gerhard | author2-link = Gerhard Ringel |
|||
| isbn = 0-12-328552-6 |
|||
| pages = 77–81 |
|||
| publisher = Academic Press |
|||
| title = Pearls in Graph Theory: A Comprehensive Introduction |
|||
| year = 1990}}. |
|||
*{{citation |
|||
| last1 = Holton | first1 = D. A. |
|||
| last2 = Sheehan | first2 = J. |
|||
| isbn = 0-521-43594-3 |
|||
| pages = 183–213 |
|||
| publisher = [[Cambridge University Press]] |
|||
| title = The Petersen Graph |
|||
| year = 1993}}. |
|||
*{{citation |
|||
| last1 = Lubotzky | first1 = A. | author1-link = Alexander Lubotzky |
|||
| last2 = Phillips | first2 = R. |
|||
| last3 = Sarnak | first3 = P. | author3-link = Peter Sarnak |
|||
| doi = 10.1007/BF02126799 |
|||
| issue = 3 |
|||
| journal = [[Combinatorica]] |
|||
| mr = 963118 |
|||
| pages = 261–277 |
|||
| title = Ramanujan graphs |
|||
| volume = 8 |
|||
| year = 1988}}. |
|||
*{{citation |
|||
| last = Tutte | first = W. T. | author-link = William Thomas Tutte |
|||
| doi = 10.1017/S0305004100023720 |
|||
| issue = 4 |
|||
| journal = Proc. Cambridge Philos. Soc. |
|||
| pages = 459–474 |
|||
| title = A family of cubical graphs |
|||
| volume = 43 |
|||
| year = 1947}}. |
|||
== Зовнішні посилання == |
|||
* [[Andries Brouwer|Brouwer, Andries E.]] [http://www.win.tue.nl/~aeb/drg/graphs/cages/cages.html Cages]{{ref-en}} |
|||
* Royle, Gordon. [http://mapleta.maths.uwa.edu.au/~gordon/remote/cages/index.html Cubic Cages] and [http://mapleta.maths.uwa.edu.au/~gordon/remote/cages/allcages.html Higher valency cages]{{ref-en}} |
|||
*{{mathworld | title = Cage Graph | urlname = CageGraph}} |
|||
[[Категорія:Види графів]] |
[[Категорія:Види графів]] |
Версія за 15:08, 28 червня 2016
n-клітка — кубічний граф обхвату n з найменшим можливим числом вершин. Граф називається кубічним, якщо з кожної його вершини виходять 3 ребра. Обхват графа — це довжина найменшого циклу в ньому.
- 3-клітка — К4, остов тетраедра, 4 вершини.
- 4-клітка — К3,3, один з двох мінімальних не планарних графів, 6 вершин.
- 5-клітка — Граф Петерсена, 10 вершин. Мінімальний кубічний граф з індексом самоперетину 2.
- 6-клітка — Граф Хівуда, 14 вершин. Розбивається на 1-фактори (тобто, реберно розфарбовуємий), будь-яка сума двох чинників утворює гамільтонів цикл. Мінімальний кубічний граф з індексом самоперетину 3.
- 7-клітка — Граф МакЖі[en], 24 вершини. Мінімальний кубічний граф з індексом самоперетину 8.
- 8-клітка — Граф Татта — Коксетера, 30 вершин.
Узагальнене визначення
(r,n)-клітка — регулярний граф ступеня r (тобто з кожної вершини якого виходить рівно r ребер) та обхвату n з найменшим можливим числом вершин.
Тривіальні сімейства
- (2,n)-клітками є, очевидно, циклічні графи Cn
- (r-1,3)-клітки — повні графи Кr з r вершин
- (r,4)-клітки — повні дводольні графи Кr,r, у яких в кожній долі знаходиться по r вершин
Нетривіальні представники
- (7,5)-клітка — Граф Гофмана-Сінглтона, 50 вершин.
Відомі ще деякі клітки. У таблиці нижче показано кількість вершин в (r,n)-клітинах ступеня 3≤r≤7 та обхвату 3≤n≤12. Клітки для цих та великих r и n описані тут: [1] (англійською мовою).
n: | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
r = 3: | 4 | 6 | 10 | 14 | 24 | 30 | 58 | 70 | 112 | 126 |
---|---|---|---|---|---|---|---|---|---|---|
r = 4: | 5 | 8 | 19 | 26 | 67 | 80 | 275 | 384 | 728 | |
r = 5: | 6 | 10 | 30 | 42 | 152 | 170 | 2730 | |||
r = 6: | 7 | 12 | 40 | 62 | 294 | 312 | 7812 | |||
r = 7: | 8 | 14 | 50 | 90 |
Графи Мура
Кількість вершин в (r,n)-клітці більше або дорівнює
- для непарних n та
- для парних.
Якщо має місце рівність, то відповідний граф називається графом Мура. У той час як клітка існує для будь-яких r > 2 і n > 2, нетривіальних графів Мура набагато менше. З вищезгаданих клітин, графами Мура є Граф Петерсена, граф Хівуда, граф Татта — Коксетера і граф Гофмана-Синглтона . Доведено,[1][2][3] що всі непарні випадки вичерпуються n = 5, r = 2, 3, 7 та, можливо, 57, а парні n = 6, 8, 12.
Примітки
Література
- Ф. Харари Теория графов. — М.: УРСС, — 2003. — 300 с — ISBN 5-354-00301-6.
Посилання
- Biggs, Norman (1993), Algebraic Graph Theory (вид. 2nd), Cambridge Mathematical Library, с. 180—190, ISBN 0-521-45897-8.
- Bollobás, Béla; Szemerédi, Endre (2002), Girth of sparse graphs, Journal of Graph Theory, 39 (3): 194—200, doi:10.1002/jgt.10023, MR 1883596.
- Exoo, G; Jajcay, R (2008), Dynamic Cage Survey, Dynamic Surveys, Electronic Journal of Combinatorics, DS16.
- Erdős, Paul; Rényi, Alfréd; Sós, Vera T. (1966), On a problem of graph theory (PDF), Studia Sci. Math. Hungar., 1: 215—235.
- Hartsfield, Nora; Ringel, Gerhard (1990), Pearls in Graph Theory: A Comprehensive Introduction, Academic Press, с. 77—81, ISBN 0-12-328552-6.
- Holton, D. A.; Sheehan, J. (1993), The Petersen Graph, Cambridge University Press, с. 183—213, ISBN 0-521-43594-3.
- Lubotzky, A.; Phillips, R.; Sarnak, P. (1988), Ramanujan graphs, Combinatorica, 8 (3): 261—277, doi:10.1007/BF02126799, MR 0963118.
- Tutte, W. T. (1947), A family of cubical graphs, Proc. Cambridge Philos. Soc., 43 (4): 459—474, doi:10.1017/S0305004100023720.
Зовнішні посилання
- Brouwer, Andries E. Cages(англ.)
- Royle, Gordon. Cubic Cages and Higher valency cages(англ.)
- Weisstein, Eric W. Cage Graph(англ.) на сайті Wolfram MathWorld.