Определение. Неориентированным графом (просто графом или неографом) называется пара множеств, первое из которых представляет собой конечное множество V, называемое множеством вершин, второе – множество Е двухэлементных подмножеств множества V, называемое множеством неориентированных рёбер (или просто рёбер).
Определение. Элемент множества Е называется неориентированным ребром (или просто ребром).
Неориентированный граф обозначается G(V, E), а для записи нескольких различных графов рекомендуется указывать, какому графу соответствует множество вершин или рёбер, например, запись V(G1) означает, что множество вершин соответствует неориентированному графу G1, запись E(G2) – множество рёбер соответствует неориентированному графу G2.
Число вершин неориентированного графа n называется порядком этого графа, другими словами, порядок неориентированного графа определяется по мощности множества вершин графа. Неориентированный граф с n вершинами и m рёбрами называется (n, m)-графом.
Наглядно неориентированный граф изображается в виде рисунка (схемы или диаграммы), на котором вершины графа изображаются в виде точек (кружочков закрашенных или полых), неориентированные рёбра – в виде отрезков (линий), связывающих соответствующие вершины, соединённые этим ребром. При изображении неориентированного графа не имеют значения радиус кружочков, изображающих вершины, а также длины отрезков, соответствующих неориентированным рёбрам. Позже будут рассмотрены другие способы задания неориентированных графов.
Определение. Размеченным называется неориентированный граф, в котором каждая вершина графа отмечена, т.е. задана так называемая функция разметки, которая каждой вершине (ребру) ставит в соответствие метку (обозначение вершины или ребра). Множество меток может разделяться на два непересекающихся подмножества: множество меток вершин и множество меток рёбер.
Пример 1. Неориентированный граф G1, показанный на рис. 1, состоит из множества вершин V(G1), содержащего 6 элементов, и множества рёбер E(G1), содержащего 6 элементов: V(G1) = {a, b, c, d, e, f}, E(G1) = {{a, b}, {a, c}, {b, d}, {c, d}, {с, e}, {d, f}}.
Неориентированный граф G2, показанный на рис. 2, состоит из множества вершин V(G2), содержащего 6 элементов, и множества рёбер E(G2), содержащего 5 элементов: V(G2) = {a, b, c, d, e, f}, E(G2) = {{a, c}, {b, e}, {c, d}, {d, e}, {d, f}}.
Неориентированный граф G3, показанный на рис. 3, состоит из множества вершин V(G3), содержащего единственный элемент, и множества рёбер E(G3), не содержащего элементов: V(G3) = {a}, E(G3) = {}.
Пример 2. Запишите множества вершин и ребер неориентированных графов, показанных на рис. 4-6, перечислением элементов.
Неориентированный граф G4 состоит из множества вершин V(G4), содержащего шесть элементов, и множества ребер E(G1), содержащего пять элементов: V(G4) = {a, b, c, d, e, f}, E(G4) = {{a, c}, {c, d}, {d, b}, {b, e}, {d, f}}.
Неориентированный граф G5 состоит из множества вершин V(G5), содержащего четыре элемента, и множества ребер E(G5), содержащего три элемента: V(G5) = {a, b, c, d}, E(G5) = {{a, c}, {a, d}, {b, d}}.
Неориентированный граф G6 состоит из множества вершин V(G6), содержащего четыре элемента, и множества ребер E(G6), не содержащего элементов: V(G6) = {a, b, c, d}, E(G6) = {}.
В качестве Упражнения рассмотрите неориентированный граф (примеры графов см. ниже), соответствующий первой букве Вашего имени (или фамилии) и запишите для него множества вершин и ребер.
Заметим, что в упражнении используются неориентированные графы с петлями, т.е. в таких графах допускается наличие так называемых петель, т.е. неориентированных ребер, которые соединяют вершину саму с собой, т.е. фактически содержат ребро {а, а}.
см. также варианты размеченных неориентированных графов по ссылке: