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

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

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

Графы дружеских отношений F₂, F₃ и F₄.

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

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

Теорема о графе дружеских отношенийПравить

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

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

Разметка и раскраскаПравить

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

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

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

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

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

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

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