36.Графы. Основные понятия.

Графом G наз. пара мн-в: G=(V,E). мн-во. V наз. вершин(непустое), а E – рёбер(возможно пустое). Мн-во Е представляет собой некоторое мн-во неупорядоченых пар вершин. Число вершин -р, кол-во ребер — q.

Есл мн-во V конечно, то граф наз. конечным. Рёбра вида (i,j) и (j,i) наз. паралельными, а рёбра вида (i,i) наз. петлёй. Граф наз. простым, если он не имеет параллельных рёбер и петель (Если имеет параллельные рёбра, то U – мульти мн-во). Вершины, связаные ребром наз. смежными. Если в графе имеется (i,j), то вершины i, j наз. инцедентными этому ребру и наоборот, ребро наз. инцедентным этим вершинам. Два ребра, имеющие общую вершину наз. смежными. Если в графе имеется ребро (i,j), то i, j – концевые вершины ребра (i,j). Число рёбер, инцедентных вершине наз. степенью вершины (deg(i)). Вершиа нулевой степени наз. изолированой, вершина первой степени наз. висячей. Граф, все вершины к-го имеют нулевую степень, наз. пустыми. Граф, любые две вершины к-госмежны наз. полным.

Два графа G и D наз. изоморфными : G  D, если  взаимно однозн. соотв. между их вершинами, сохр. смежность(G=(N,U), D=(M,W); f:NM; (i,j)G (f(i),f(j))W).

Очевидно что ni=1­­­deg(i)=2m, где n – число вершин, m – число рёбер.

Подграфом D графа G (DG) наз. граф, такой, что MN; WU.

Граф D наз. остовным подграфом графа G, если M=N. Пусть G=(N,U) и TN.

Вершинопорждённым подграфом графа G с порждающим мн-вом T: G(T), наз. подграфом графа G с мн-вом рёбер W: G(T)=(T,W) такой, что две вершины G(T) смежны тогда и только тогда, когда они смежны в исходном графе.

Типы задач:Примеры известных задач, которые способствовали развитию теории графов. Раскраска графов. Правильная рас краска дводольного графа.

1)Задача о Кёнигсбергских мостах:

Можно ли обойти все 7 мостов пройдя по каждому 1 раз, вернувшись в начальную точку маршрута (любую) не переплывая реки? (Нет)

Можно ли пройти по всем 7 мостам по 1 разу, не обязательно вернувшись в начальную точку?(Нет)

2)Задача о 3 домах и 3 колодцах.

Необходимо от каждого дома к каждому колодку проложить тропу таким образом чтобы тропы не пересекались.

3)Задача о 4 красках. (Правильная раскраска графа.) Эта задача является одной из наиболее известных проблем теории графов, которая оставалась неразрешимой на протяжении длительного времени. Возникла она в связи с раскраской географических карт и состоит в след.: Произвольную географическую карту на плоскости необходимо раскрасить используя лишь 4 различных цвета таким образом, чтобы любые 2 соседние области на карте были покрашены в различные цвета.

Известно что для такой раскраски достаточно 5 красок. (теорема о 5 красках). Известно также что для такой раскраски гарантировано недостаточно 3 красок. Вопрос о 4 красках был положительно разрешен в 1976 году.  Это была первая крупная математическая теорема, для доказательства которой был применён компьютер. Несмотря на последующие упрощения, доказательство практически невозможно проверить, не используя компьютер. Поэтому некоторые математики отнеслись к этому доказательству с недоверием, что объяснялось не только использованием компьютера, но и громоздкостью описания алгоритма первых доказательств, впоследствии были предложены более компактные алгоритмы и скорректирован ряд ошибок.

Вершинная раскраска графов называется правильной если смежные вершины получают различные цвета. Задача раскраски графа состоит в определении минимального количества цветов в которое можно правильно покрасить вершины заданного графа.

Если граф двудольный, то существует правильная раскраска графа 2 цветами. Верно и обратное утверждение.