Матрица смежности, матрица инцендентностей, список смежности

Неориентированные, ориентированные графы. Способы задания графов.

ГРАФЫ

Определение. Неориентированным графом называют пару , где – множество вершин графа, – множество неориентированных ребер графа, и последнее множество есть некоторое подмножество множества всех неупорядоченных пар вершин .

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

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

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

Определение. Ориентированным графом называют пару , где – множество вершин графа, – множество упорядоченных пар вершин – ориентированных ребер, и это есть некоторое подмножество декартова произведения :

Пример. Множество вершин состоит из трех элементов . Тогда упорядоченными парами вершин будут следующие:

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

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

Дата добавления: 2017-01-13