Граф дружеских отношений

Граф дружеских отношений
Вершин	2n+1
Рёбер	3n
Радиус	1
Диаметр	2
Обхват	3
Хроматическое число	3
Хроматический индекс	2n
Свойства	Граф единичных расстояний планарный эйлеров фактор-критический
Обозначение	Fn
Медиафайлы на Викискладе

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

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

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

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

Комбинаторное доказательство теоремы о графе дружеских отношений дали Мертциос и Унгер^[6]. Другое доказательство дал Крейг Хунеке^[7].

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

Граф дружеских отношений F_n имеет совершенную разметку рёбер тогда и только тогда, когда n нечётно. Он имеет грациозную разметку тогда и только тогда, когда n ≡ 0 (mod 4), или n ≡ 1 (mod 4)^[8][9].

Любой граф дружеских отношений является фактор-критическим.

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

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

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

У этой статьи есть несколько проблем, помогите их исправить: Необходимо проверить качество перевода c неуказанного языка, исправить содержательные и стилистические ошибки. Вы можете помочь улучшить эту статью (см. также рекомендации по переводу). Оригинал не указан. Пожалуйста, укажите его. (3 июля 2017) Стиль этой статьи неэнциклопедичен или нарушает нормы литературного русского языка. Статью следует исправить согласно стилистическим правилам Википедии. (3 июля 2017) Пожалуйста, после исправления проблемы исключите её из списка параметров. После устранения всех недостатков этот шаблон может быть удалён любым участником.