3.01.1. Элементы теории графов. 1. Основные определения и типы графов. Основные понятия

Пусть V – конечное непустое множество и Е Í{{U, V}ç U,VÎV, U¹V}-- множество его двухэлементных подмножеств. Пара G = (V, E) называется Графом. Множество V=V(G) при этом называется множеством Вершин графа G, а его элементы -- вершинами; множество Е=Е(G) называется множеством Ребер графа G, а его элементы -- ребрами. И вершины, и ребра графа G называются его элементами. Поэтому если U -- вершина графа G, а Е -- ребро G, то вместо UÎV(G), EÎE(G) можно писать UÎG, EÎG.

Если E = {U, V} -- ребро графа G ( пишут также Е = Uv ), то вершины U И V называются концами ребра Е.

Графы удобно изображать в виде рисунков, на которых вершинам соответствуют отмеченные точки (или кружочки), а ребрам -- непрерывные линии, соединяющие соответствующие вершины (см. рис.).

Вершины U и V графа G называется Смежными, если {U, V}Î E(G), т. е. если они соединены ребром. Два ребра, в свою очередь, называются Смежными, Если они имеют общий конец. Если вершина V является концом ребра E, то V и E называются Инцидентными.

Мощность ú V(G)ú множества вершин V(G) называется Порядком графа G и обозначается ú Gú. Если ú V(G)ú = N и ú E(G)ú =M, то граф G Называется (N,M)-графом.

< Предыдущая		Следующая >