Теорема Рамсея.

В любом графе на 6-ть вершин либо его дополнении имеется полный трехвершинный подграф.

Док-во: Пусть x – произвольная вершина. Предположим, то x смежна с вершинами a,y,z в графе G, если б это было не так, то вершина x была бы смежна с этими вершинами в графе G., и мы начали рассмотрение с графа G. Если какие-либо 2 вершины из a,y,z смежны между собой, то граф G имеет треугольник. Если a,y,z не смежны между собой, то тогда в графе G они образуют треугольник. Обобщая теорему Рамсея можно поставить вопрос: какое наименьшее значение n(k,t) в котором каждый граф с числом вершин n содержит полный подграф с k вершинами и полный подграф с t вершинами в G.

3. Задание графов с помощью матриц.

Граф можно задавать с помощью матриц смежности вершин и ребер, матриц соседства вершин и ребер и матриц инцидентности.

Матрица смежности вершин графа.

Представляет собой квадратную бинарную матрицу, строки и столбцы которой помечены вершинами графа:

Матрица смежности вершин неориентированных графов симметрична относительно главной диагонали, а сумма ед. по каждой строке или по столбцу дает степень вершины.

Матрица соседства вершин отличается от матрицы смежности тем, что вместо единиц ставится название ребер, посредством которых смежны эти вершины.

Матрица смежности ребер аналогична матрице смежности вершин.

Представляет собой квадратную бинарную матрицу, строки и столбцы которой помечены ребрами графа:

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

Матрица соседства ребер получается из матрицы смежности, если вместо единиц поставить названия вершин, посредством которых осуществляется смежность ребер.

Матрица инцидентности – прямоугольная матрица размером n*m, n – число вершин, m – число ребер. Строки помечены вершинами графа, столбцы помечены ребрами графа. Матрице инцидентности можно поставить в соответствие граф инцидентности. Он строится след. образом: вершины исходного графа принимаются за вершины графа инцидентности, ребра исх. графа тоже принимаются за вершины графа инцидентности, они соединяются друг с другом, если соответствующая пара «вершина-ребро» инциденты в исходном графе.

4. Связность графов. Метод выделения всех маршрутов заданной длины. Теорема.

Пусть дан граф G=(X, U, F). Конечная последовательность вида x0u1x1u2…xl-1ulxl наз. маршрутом, если истинно высказывание F (x0,u1,x1)&F(x1,u2,x2)&…&F(xl-1,ul,xl).

Каждые два соседних ребра в маршруте имеют общую вершину. Число ребер в маршруте наз. его длиной (l). Если x0=xl – то маршрут циклический.

Маршрут наз. цепью, а циклический маршрут – циклом, если он не содержит повторяющихся ребер.

Цепь и цикл наз. простыми, если они не содержат повторяющихся вершин, кроме начальной и конечной для цикла. Простая цепь наз. максимальной, если она не является частью какой-либо другой простой цепи. Самая длинная из максимальных простых цепей наз. наибольшей.

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