4.2 Определение графа.

Графом G{V,E) называется совокупность двух множеств — непустого множества V (множества вершин) и множества Е неупорядоченных пар различных элементов множества V (Е — множество ребер).

Число вершин графа G обозначим р, а число ребер — q

.

3. Смежность.

Пусть v₁, v₂ — вершины, е = (v₁, v₂) — соединяющее их ребро. Тогда вершина v₁ и ребро е инцидентны, вершина v₂ и ребро е также инцидентны.

Два ребра, инцидентные одной вершине, называются смежными; две вершины, инцидентные одному ребру, также называются смежными.

Множество вершин, смежных с вершиной v, называется множеством смежности вершины v и обозначается :

3. Графическое изображение графа.

Обычно граф изображают диаграммой: вершины — точками (или кружками), ребра — линиями.

Пример.

На рис. 3 приведен пример диаграммы графа, имеющего четыре вершины и пять ребер. В этом графе вершины v₁ и v₂, v₂ и v₃, v₃ и v₄, v₄ и v₁, v₂ и v₄ смежны, а вершины v₁ и v₃ не смежны. Смежные ребра: е₁ и е₂, е₂ и е₃, е₃ и е₄, е₄ и е₁, е₁ и е₅, е₂ и е₅, е₃ и е₅, е₄ и е₅. Несмежные ребра е₁ и е₃, е₂ и е₄.

Рис. 3. Диаграмма графа

4.5 Основные определения теории графов.

1. Если элементами множества Е являются упорядоченные пары, то граф называется ориентированным (или орграфом), В этом случае элементы множества V называются узлами, а элементы множества Е — дугами.

2. Если элементом множества Е может быть пара одинаковых (не различных) элементов V, то такой элемент множества Е называется петлей, а граф называется графом с петлями (или псевдографом).

3. Если Е является не множеством, а набором, содержащим несколько одинаковых элементов_, то эти элементы называются кратными ребрами, а граф называется мультиграфом.

4. Если элементами множества Е являются не обязательно двухэлементные, а любые подмножества множества V, то такие элементы множества Е называются гипердугами, а граф называется гиперграфом.

5. Если задана функция F: V → М и/или F: Е → М, то множество М называется множеством пометок, а граф называется помеченным (или нагруженным). В качестве множества пометок обычно используются буквы или целые числа.

3. Представление графа в эвм матрицей смежности.

Представления иллюстрируются на конкретных примерах графа G и орграфа D, диаграммы которых представлены на рис. 5.

Рис. 5. Диаграммы графа (слева) и орграфа (справа), используемых в качестве примеров

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

Пример.

Представим граф G и орграф D матрицами смежности.

Тема 5 комбинаторные задачи

5.1 Комбинаторные конфигурации.

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