График дружбы

График дружбы
График дружбы
	Граф дружбы F 8 .
Вершины	2н 1 +
Края	3 н
Радиус	1
Диаметр	2
Обхват	3
Хроматическое число	3
Хроматический индекс	2 н
Характеристики	Расстояние единицы ; Планарный ; Эйлеров ; Фактор-критичный ; Локально линейный ;
Обозначения	Ф н
	Таблица графиков и параметров

В математической области теории графов граф дружбы (или граф голландской ветряной мельницы или $n$ -веер ) $F n$ представляет собой плоский неориентированный граф с $2 n + 1$ вершиной и $3 n$ ребрами. ^[1]

Граф дружбы $F n$ может быть построен путем соединения $n$ копий графа циклов $C 3$ с общей вершиной, которая становится универсальной вершиной для графа. ^[2]

По построению граф дружбы $F n$ изоморфен ) графу ветряной мельницы $3, n Wd ($ . Это единичное расстояние с обхватом 3, диаметром 2 и радиусом 1. Граф $F 2$ изоморфен графу-бабочке . Графы дружбы обобщаются треугольными графами кактусов .

Теорема о дружбе

Теорема дружбе о Пола Эрдеша , Альфреда Реньи и Веры Т. Сос ( 1966 ). ^[3] утверждает, что конечные графы, у которых каждые две вершины имеют ровно одного общего соседа, являются в точности графами дружбы. Неформально, если группа людей обладает тем свойством, что каждая пара людей имеет ровно одного общего друга, то должен быть один человек, который является другом для всех остальных. Однако для бесконечных графов может существовать множество разных графов одинаковой мощности, обладающих этим свойством. ^[4]

Комбинаторное доказательство теоремы о дружбе было дано Мерциосом и Унгером. ^[5] Другое доказательство было дано Крейгом Ханеке. ^[6] Формализованное доказательство в Metamath было опубликовано Александром ван дер Векенсом в октябре 2018 года в списке рассылки Metamath. ^[7]

Маркировка и окраска

Граф дружбы имеет хроматический номер 3 и хроматический индекс $2 n$ . Его хроматический многочлен выводится из хроматического многочлена графа цикла $C 3$ и равен

(x-2)^{n}(x-1)^{n}x

.

Граф дружбы $Fn n$ является изящным тогда и только тогда, когда $нечетно$ . Это изящно тогда и только тогда, когда $n \equiv 0 (mod 4)$ или $n \equiv 1 (mod 4)$ . ^[8]^[9]

Каждый граф дружбы фактор-критичен .

Экстремальная теория графов

Согласно экстремальной теории графов , каждый граф с достаточным количеством ребер (относительно количества вершин) должен содержать $k$ -веер как подграф. Более конкретно, это справедливо для $n$ -вершинный граф, если число ребер равно

\left\lfloor {\frac {n^{2}}{4}}\right\rfloor +f(k),

где $f(k)$ является $k^{2}-k$ если $k$ странно, и $f(k)$ является $k^{2}-3k/2$ если $k$ четный. Эти оценки обобщают теорему Турана о количестве ребер в графе без треугольников и являются наилучшими возможными оценками для этой задачи, поскольку для любого меньшего числа ребер существуют графы, которые не содержат $k$ -вентилятор. ^[10]

Обобщения

Любые две вершины, имеющие ровно одного общего соседа, эквивалентны тому, что любые две вершины соединены ровно одним путем длиной два.Это было обобщено на $P_{k}$ -графы, в которых любые две вершины соединены уникальным путем длины $k$ . Для $k\geq 3$ такие графы неизвестны, и утверждение об их отсутствии является гипотезой Коцига .

Ссылки

^ Вайсштейн, Эрик В. , «График голландской ветряной мельницы» , MathWorld
^ Галлиан, Джозеф А. (3 января 2007 г.), «Динамический обзор разметки графов», Электронный журнал комбинаторики : DS6, doi : 10.37236/27 .
^ Эрдос, Пол ; Реньи, Альфред ; Сос, Вера Т. (1966), «Об одной задаче теории графов» (PDF) , Studia Sci. Венгерский. , 1 : 215–235 .
^ Хватал, Вацлав ; Коциг, Антон ; Розенберг, Иво Г.; Дэвис, Рой О. (1976), «Есть $\scriptstyle 2^{\aleph _{\alpha }}$ Графики дружбы кардинала $\scriptstyle \aleph _{\alpha }$ ", Canadian Mathematical Bulletin , 19 (4): 431–433, doi : 10.4153/cmb-1976-064-1 .
^ Мерциос, Джордж; Уолтер Унгер (2008), «Проблема дружбы на графах» (PDF) , Отношения, порядки и графики: взаимодействие с информатикой
^ Хунеке, Крейг (1 января 2002 г.), «Теорема о дружбе», The American Mathematical Monthly , 109 (2): 192–194, doi : 10.2307/2695332 , JSTOR 2695332
^ ван дер Векенс, Александр (11 октября 2018 г.), «Теорема о дружбе (№ 83 из «списка 100 теорем»)» , список рассылки Metamath
^ Бермонд, Ж.-К.; Брауэр, AE ; Джерма, А. (1978), «Триплетные системы и связанные с ними различия», Комбинаторные задачи и теория графов (Университет Орсе, 1976) , Colloq. Стажер. CNRS, вып. 260, CNRS, Париж, стр. 35–38, МР 0539936 .
^ Бермонд, Ж.-К.; Коциг, А .; Турджен, Дж. (1978), «Об одной комбинаторной задаче антенн в радиоастрономии», Комбинаторика (Труды пятого венгерского коллоквиума, Кестхей, 1976), Vol. I , Colloq. Математика. Сок. Янош Бояи, том. 18, Северная Голландия, Амстердам-Нью-Йорк, стр. 135–149, МР 0519261 .
^ Эрдеш, П .; Фюреди, З. ; Гулд, Р.Дж .; Гундерсон, Д.С. (1995), «Экстремальные графы для пересекающихся треугольников» , Журнал комбинаторной теории , серия B, 64 (1): 89–100, doi : 10.1006/jctb.1995.1026 , MR 1328293 .

[1] Вайсштейн, Эрик В. , «График голландской ветряной мельницы» , MathWorld

[2] Галлиан, Джозеф А. (3 января 2007 г.), «Динамический обзор разметки графов», Электронный журнал комбинаторики : DS6, doi : 10.37236/27 .

[3] Эрдос, Пол ; Реньи, Альфред ; Сос, Вера Т. (1966), «Об одной задаче теории графов» (PDF) , Studia Sci. Венгерский. , 1 : 215–235 .

[4] Хватал, Вацлав ; Коциг, Антон ; Розенберг, Иво Г.; Дэвис, Рой О. (1976), «Есть $\scriptstyle 2^{\aleph _{\alpha }}$ Графики дружбы кардинала $\scriptstyle \aleph _{\alpha }$ ", Canadian Mathematical Bulletin , 19 (4): 431–433, doi : 10.4153/cmb-1976-064-1 .

[5] Мерциос, Джордж; Уолтер Унгер (2008), «Проблема дружбы на графах» (PDF) , Отношения, порядки и графики: взаимодействие с информатикой

[6] Хунеке, Крейг (1 января 2002 г.), «Теорема о дружбе», The American Mathematical Monthly , 109 (2): 192–194, doi : 10.2307/2695332 , JSTOR 2695332

[7] ван дер Векенс, Александр (11 октября 2018 г.), «Теорема о дружбе (№ 83 из «списка 100 теорем»)» , список рассылки Metamath

[8] Бермонд, Ж.-К.; Брауэр, AE ; Джерма, А. (1978), «Триплетные системы и связанные с ними различия», Комбинаторные задачи и теория графов (Университет Орсе, 1976) , Colloq. Стажер. CNRS, вып. 260, CNRS, Париж, стр. 35–38, МР 0539936 .

[9] Бермонд, Ж.-К.; Коциг, А .; Турджен, Дж. (1978), «Об одной комбинаторной задаче антенн в радиоастрономии», Комбинаторика (Труды пятого венгерского коллоквиума, Кестхей, 1976), Vol. I , Colloq. Математика. Сок. Янош Бояи, том. 18, Северная Голландия, Амстердам-Нью-Йорк, стр. 135–149, МР 0519261 .

[10] Эрдеш, П .; Фюреди, З. ; Гулд, Р.Дж .; Гундерсон, Д.С. (1995), «Экстремальные графы для пересекающихся треугольников» , Журнал комбинаторной теории , серия B, 64 (1): 89–100, doi : 10.1006/jctb.1995.1026 , MR 1328293 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]