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

Friendship graph
График дружбы
График дружбы 8.svg
Граф дружбы F8.
Вершины2n + 1
Края3n
Радиус1
Диаметр2
Обхват3
Хроматическое число3
Хроматический индекс2n
Характеристики
ОбозначениеFп
Таблица графиков и параметров
Графики дружбы F2, F3 и F4.

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

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

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

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

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

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

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

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

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

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

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

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

куда является если странно, и является если даже. Эти оценки обобщают Теорема Турана от количества ребер в граф без треугольников, и они являются наилучшими возможными оценками этой проблемы, поскольку для любого меньшего числа ребер существуют графы, не содержащие -поклонник.[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), «Есть графы дружбы кардинала ", Канадский математический бюллетень, 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.