Реферат: Элементы комбинаторики. Правила умножения и сложения

Изоморфные графы имеют одинаковое число вершин, ребер, степени соответствующих вершин равны.

16. Способы задания графов.

В общем виде «задать граф» означает: описать множество его вершин и ребер, а также отношение инцидентности.

Способы задания графа:

1. Графический

2. Перечислением вершин и ребер.

3. Задание графа матрицей инцидентности. Строки матрицы характеризуют вершины графа, столбцы – ребра графа.

Для неориентир графа: 1 – если вершина и ребро инцидентны, 0 – если не инциндентна.

Для ориентир - -1 если вершина является началом ребра, 1 – если концом ребра, 0 – не инциндентны, 2 – ребро – петля.

4. Задание графа матрицей смежности.

Матрица смежности – это квадратная матрица размера n*n, которая по горизонтали и по вертикали учитывает все вершины графа.

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

5. Задание графа матрицей весов.

Матрица весов - вариант матрицы смежности для взвешенного графа, представляет собой квадратную матрицу размером n n (n - число вершин), (i,j)-й элемент которой равен весу ребра / дуги (v , v), если таковое имеется в графе; в противном случае (i,j)-й элемент полагается равным нулю или бесконечности в зависимости от решаемой задачи.

17. Маршруты и циклы. Связность.

Маршрутом называется последовательность вершин и ребер, в которой любые 2 соседних элемента инцидентны.

Если в простом графе маршрут задан последовательностью вершин , то вершины и называются концами маршрута.

Маршрут называется замкнутым, если . Незамкнутым - если

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

Граф, у которого любые 2 его вершины являются смежными, называется полным графом.

Маршрут(для ориентир графа), дуги которого различны, называется путем.

Длинной маршрута называется число ребер графа с учетом повторений.

Две вершины называются связными, если их соединяет хотя бы одна простая цепь.

Отношение связности – это отношение эквивалентности.

Граф, называют связным, если любые 2 его вершины можно соединить простой цепью.

Ребро называют перешейком, если после его удаления граф теряет свойство связности, т.е. распадается на 2 компонента связности.

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

Ориентированный граф называют слабо связным, если явл связным граф, получающийся из орграфа заменой всех его дуг на ребра.

18. Эйлеровы и гамильтоновы графы.