График дружбы - Friendship graph

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

Графики дружбы F₂, F₃ и F₄.

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

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

По построению граф дружбы F_п изоморфен график ветряка Wd (3, п). это единичное расстояние с обхватом 3, диаметром 2 и радиусом 1. График F₂ изоморфен график бабочки.

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

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

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

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

График дружбы имеет хроматическое число 3 и хроматический индекс 2n. Его хроматический полином можно вывести из хроматического полинома графа циклов C₃ и равен ${\displaystyle (x-2)^{n}(x-1)^{n}x}$.

Граф дружбы F_п является грациозный если и только если п странно. это изящный если и только если п ≡ 0 (мод 4) или п ≡ 1 (мод.4).^[8][9]

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

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

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

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

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

Рекомендации

1. Вайсштейн, Эрик В. "Голландский график ветряных мельниц". MathWorld.
2. Галлиан, Дж. А. (3 января 2007 г.), «Динамическое обследование DS6: разметка графиков» (PDF), Электронный журнал комбинаторики, DS6, 1-58, заархивировано из оригинал (PDF) 31 января 2012 г., получено 16 сентября, 2009.
3. Эрдеш, Пол; Реньи, Альфред; Сос, Вера Т. (1966), «К проблеме теории графов» (PDF), Studia Sci. Математика. Hungar., 1: 215–235.
4. Хваталь, Вацлав; Коциг, Антон; Розенберг, Иво Г .; Дэвис, Рой О. (1976), «Есть ${\displaystyle \scriptstyle 2^{\aleph _{\alpha }}}$ графы дружбы кардинала ${\displaystyle \scriptstyle \aleph _{\alpha }}$", Канадский математический бюллетень, 19 (4): 431–433, Дои:10.4153 / cmb-1976-064-1.
5. Мерциос, Джордж; Уолтер Унгер (2008), «Проблема дружбы на графах» (PDF), Связи, порядки и графики: взаимодействие с информатикой
6. Хунеке, Крейг (1 января 2002 г.), «Теорема о дружбе», Американский математический ежемесячник, 109 (2): 192–194, Дои:10.2307/2695332, JSTOR  2695332
7. ван дер Векенс, Александр (11 октября 2018 г.). «Теорема о дружбе (№83 из« 100 теорем списка »)». [email protected] (Список рассылки).
8. Bermond, J.-C .; Брауэр, А.Э.; Germa, A. (1978), "Systèmes de triplets et différences associées", Problèmes Combinatoires et Théorie des Graphes (Univ. Orsay, 1976), Коллок. Междунар. дю CNRS, 260, CNRS, Париж, стр. 35–38, МИСТЕР  0539936.
9. Bermond, J.-C .; Коциг, А.; Turgeon, J. (1978), "О комбинаторной задаче антенн в радиоастрономии", Комбинаторика (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. я, Коллок. Математика. Soc. Янош Бойяи, 18, Северная Голландия, Амстердам-Нью-Йорк, стр. 135–149, МИСТЕР  0519261.
10. Эрдеш, П.; Фюреди, З.; Гулд, Р. Дж.; Гундерсон, Д. С. (1995), «Экстремальные графики для пересекающихся треугольников», Журнал комбинаторной теории, Серия B, 64 (1): 89–100, Дои:10.1006 / jctb.1995.1026, МИСТЕР  1328293.