ГУО «Смолевичская районная гимназия»

ГУО «Смолевичская районная гимназия»

Задача № 11 «Треугольники в графах»

Резюме

1) В первом пункте мы нашли число треугольников в полном графе с вершинами, вывели формулу для нахождения количества треугольников в полном графе и в дополнение к доле.

2) Во втором пункте мы нашли число треугольников в графе G, который содержит n вершин , причем пара{ v_i, v_j } Î E тогда только тогда, когда, или (геометрически этот граф можно представить как выпуклый многоугольник, в котором проведены все диагонали, а все стороны стерты).

3) В третьем пункте мы нашли число t (G) треугольников в полном двудольном графе G, доли которого содержат m ₁ и m ₂ вершин соответственно, а также нашли число t () треугольников в дополнении к такому графу.

4) В четвёртом пункте мы нашли число t (G) треугольников в полном трёхдольном, четырёхдольном, S-дольном графе G, а также нашли число t () треугольников в дополнении к таким графам.

Условие

Обыкновенным графом называется пара , где V – некоторое непустое конечное множество, E – множество неупорядоченных пар различных элементов из V. Элементы множества V называются вершинами графа, элементы множества E – его ребрами. Множество вершин графа G будем обозначать через V (G), множество ребер – E (G), число вершин – n (G), которое также называется порядком графа, число ребер – m (G). Говорят, что две вершины u и v графа смежны, если множество { u, v } является ребром и не смежны в противном случае. Множество вершин, смежных с заданной вершиной, называется окружением этой вершины. Дополнением (дополнительным графом) к графу называется граф , у которого множество вершин то же, что у G, и две различные вершины смежны в графе тогда и только тогда, когда они несмежны в графе G. Тройка { u, v, w } вершин графа называется треугольником, если неупорядоченные пары { u, v }, { u, w }, { v, w } являются ребрами этого графа. Обозначим через t (G) число треугольников в графе G.

Начальные задачи.

1) Найдите число t (G) треугольников в полном графе G с n вершинами.

2) Пусть граф G содержит n вершин , причем пара{ v_i, v_j } Î E тогда только тогда, когда, или (геометрически этот граф можно представить как выпуклый многоугольник, в котором проведены все диагонали, а все стороны стерты). Найдите число t (G) треугольников в таком графе.

3) Найдите число t (G) треугольников в полном двудольном графе G, доли которого содержат m ₁ и m ₂ вершин соответственно, а также найдите число t () треугольников в дополнении к такому графу.

4) Те же вопросы, что и в пункте 3) для трехдольного графа, четырехдольного графа и т.п.

Сложные задачи.

5) Проверьте, что для графов из пп. 1) – 4) и их дополнений имеет место следующая формула

, (1)

где , и – степень вершины x в графе G, т. е. число вершин графа G, смежных с вершиной x.

6) Докажите формулу (1) в общем случае.

7) Используя формулу (1), попытайтесь найти достижимую нижнюю оценку на величину в терминах числа вершин графа G. Приведите примеры графов, подтверждающих достижимость найденной оценки.

8) Предложите свои направления и обобщения этой задачи и исследуйте их.

Возможные направления.

9) Пусть G – кубический граф, т. е. степень каждой его вершины равна 3, который является графом пересечений ребер некоторого другого графа H. Другими словами, и две вершины в графе G смежны в том и только в том случае, если соответствующие им ребра в графе H имеют общую вершину. Попытайтесь найти точное значение параметра в терминах числа вершин графа G или получите оценки этого параметра.

10) Пусть P – класс графов. Граф G назовем локально P - графом, если для любой его вершины подграф, порожденный окружением этой вершины, принадлежит классу P. (Подграф, порожденный окружением некоторой вершины v, – это граф, вершинами которого являются все вершины из окружения вершины v, а ребрами – все ребра исходного графа, соединяющие вершины, принадлежащие окружению вершины v).

Обозначим через Local (P) класс всех локально P -графов и введем в рассмотрение следующие параметры:

,

.

Для различных классов P найдите точные значения параметров и или предложите оценки этих параметров. В качестве классов P можно рассмотреть следующие классы графов: простые циклы, простые цепи, деревья, ациклические графы, двудольные графы, граф r -мерного булева куба, k -регулярные графы (), связные графы, несвязные графы, гамильтоновы графы, планарные графы или любые другие известные классы графов. Используя результаты проведенного исследования, установите необходимые условия существования локально P -графов. В частности, докажите следующие утверждения: 1) не существует локально k -регулярного графа с m ребрами в случае, когда оба параметра k и m не делятся на 3; 2) если для заданного графа H граф G является локально H -графом и m (H) не делится на 3, то n (G) делится на 3.

Решение

1) Найдите число t (G) треугольников в полном графе G с n вершинами.

Для полного графа характерно наличие всевозможных ребер для каждой вершины. То есть окружением любой вершины является множество всех вершин графа кроме неё самой.

Если вершин n, то каждая соединена ребром с (n-1) вершиной. Тогда любые два ребра, одним из концов которого является рассматриваемая вершина, являются двумя сторонами, какого-то треугольника, а третья сторона всегда существует, так как граф полный. Общее количество треугольников в полном графе (в дополнение к доле) есть выборка по 3 элемента из количества вершин, то есть ().

2) Пусть граф G содержит n вершин , причем пара{ v_i, v_j } Î E тогда только тогда, когда, или (геометрически этот граф можно представить как выпуклый многоугольник, в котором проведены все диагонали, а все стороны стерты). Найдите число t (G) треугольников в таком графе.

Как известно из каждой вершины многоугольника можно провести (n-3) диагонали.

Следует также учитывать тот факт, что если взяты диагонали из одной вершины к соседним между собой вершинам многоугольника, то треугольники не будут существовать, так как стороны многоугольника отсутствуют в исходном графе. Тогда:

3) Найдите число t (G) треугольников в полном двудольном графе G, доли которого содержат m ₁ и m ₂ вершин соответственно, а также найдите число t () треугольников в дополнении к такому графу.

Напомним некоторые определения теории графов:

Опр.1. Двудольный граф или биграф - это граф, множество вершин которого можно разбить на две части таким образом, что каждое ребро графа соединяет какую-то вершину из одной части с какой-то вершиной другой части (доли), то есть не существует ребра, соединяющего две вершины из одной и той же части.

Опр.2. Двудольный графназывается полным двудольным (биклика), если каждая вершина одной доли соединена ребром с каждой вершиной другой доли и наоборот.(Wikipedia.ru)

1. Одним из свойств двудольного графа является отсутствие цикла нечётной длины, то есть треугольника с заданным условием не существует.

2. Найдём :

- будет граф, состоящий из двух полных подграфов с и вершинами. Формулу для t(G) полного графа мы вывили в п. 1).

Обозначим подграф с вершинами , а с .

Тогда = + ведь треугольников со сторонами, соединёнными вершинами разных долей не будет.

Следует заметить, что , так как в противном случае треугольник вообще построить нельзя.

4) Те же вопросы, что и в пункте 3) для трехдольного графа, четырехдольного графа и т.п.

S дольные графы.

1. S=3 (трёхдольный граф)

Рассмотрим для полного трёхдольного графа с количеством вершин в долях

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

То есть

Что касается графа , то, как и в п. 3), каждая доля является отдельным подграфом, и количество треугольников в каждой из них можно найти по формуле, выведенной в п. 1) и сложить полученные результаты. Тогда получим:

2. S=4

Из полного четырёхдольного графа можно выделить полных трёхдольных подграфа. Для каждого такого подграфа набор треугольников будет свой, поэтому сумма треугольников в всевозможных трёхдольных подграфах графа G будет равна количеству треугольников графа G. Тогда:

Для , как и в любом k-дольном полном графе, каждая доля есть полный подграф, а других рёбер нет. Тогда:

3. S=k

Для полного k-дольного графа к G и его дополнения рассуждения, как и для четырёхдольного графа. Тогда в k-дольном G будет полных трёхдольных подграфов и

И

Дата добавления: 2015-08-29