WikiSort.ru - Не сортированное

Граф дружеских отношений
Вершин	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].

Примечания

Литература

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка. Исправить статью согласно стилистическим правилам Википедии.