yandex rtb 1
ГоловнаЗворотній зв'язок
yande share
Главная->Математика і інформатика->Содержание->4.1 Общие понятия и определения

Дискретная математика

4.1 Общие понятия и определения

 

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

G(V,E) = < V; E >, n(V) > 0, E c V x V

для неориентированного графа E = E^(-1) (бинарное  отношение Е - симметрично).

Минимальный граф  состоит из одной вершины.

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

Пусть v1 и v2 - вершины, e = (v1,v2) - соединяющее  их  ребро.

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

Обычно граф изображают в виде диаграммы:  вершины  -  точками, ребра - линиями, соединяющими инцидентные вершины.

 

 

20