Определение. Если {а, b} – неориентированное ребро, тогда вершины а и b называются концами или концевыми вершинами ребра {а, b}.
Ребро {а, b} называют также инцидентным вершинам а и b.
Обратно, говорят, что вершины а и b инцидентны к ребру {а, b}.
Пример 1. В неориентированном графе G1 (см. рис. ниже) вершина а инцидентна рёбрам{a, c} и {a, b}, вершина b инцидентна двум рёбрам {a, b} и{b, d}, вершина с инцидентна трём рёбрам {a, c}, {c, d} и {c, е}, вершина d инцидентна трём рёбрам {b, d}, {c, d} и {d, f}, вершина e инцидентна ребру {c, e}, вершина f инцидентна ребру {d, f}.
Пример 2. В неориентированном графе G1 ребро {a, b} инцидентно вершинам a и b, ребро {a, c} инцидентно вершинам a и c, ребро {b, d} инцидентно вершинам b и d, ребро {c, d} инцидентно вершинам c и d, ребро {c, e} инцидентно вершинам c и e, ребро {d, f} инцидентно вершинам d и f.
Пример 3. В неориентированном графе G2 (см. рис. ниже) вершина а инцидентна ребру {a, c}, вершина b инцидентна ребру {b, e}, вершина с инцидентна двум рёбрам {a, c} и {c, d}, вершина d инцидентна трём рёбрам {c, d}, {d, e} и {d, f}, вершина e инцидентна двум рёбрам {b, e} и {d, e}, вершина f инцидентна ребру {d, f}.
В неориентированном графе G2 ребро {a, c} инцидентно вершинам a и c, ребро {b, e} инцидентно вершинам b и e, ребро {c, d} инцидентно вершинам c и d, ребро {d, e} инцидентно вершинам d и e, ребро {d, f} инцидентно вершинам d и f.
Определение. Степенью вершины v, принадлежащей неориентированному графу, обозначается deg(v), называется число рёбер, инцидентных этой вершине. Список степеней всех вершин неориентированного графа называют его степенной последовательностью. Вершина степени 0 называется изолированной. Вершина степени 1 называется концевой, а ребро, инцидентное концевой вершине, называется концевым.
Пример 4. В неориентированном графе G1 (рис. ниже) степени каждой вершины определены, как показано в таблице 1 ниже.
Из информации, показанной в таблице 1 видно, что изолированных вершин в графе G1 нет, а концевых вершин две: вершина e и вершина f.
Рассмотрим граф G2 (рис. ниже).
В неориентированном графе G2 степени каждой вершины определены, как показано в таблице 2 ниже.
Из информации, показанной в таблице 2 видно, что изолированных вершин в графе G2 нет, а концевых вершин три: вершина a, вершина b и вершина f.
Определение. Две вершины называются смежными, если они инцидентны одному ребру, т.е. являются концами одного и того же ребра. Два ребра называются смежными, если они инцидентны общей вершине.
Определение. Множество вершин графа, смежных с вершиной v, обозначается adj(v).
Пример 5. В неориентированном графе G1 смежными являются следующие пары вершин: a и c, a и b, c и d, c и e, b и d, d и f, множества каждой вершины графа G1 занесены в табл. 3. Не являются смежными, например, вершины а и e, а также b и f.
В графе G1 смежными являются следующие пары неориентированных рёбер: {a, c} и {a, b}, {a, b} и {b, d}, – а также тройки {a, c}, {c, d}, {c, e} и {b, d}, {c, d}, {d, f}. Не являются смежными, например, рёбра {a, c} и {b, d}.
Пример 6. В неориентированном графе G2 смежными являются следующие пары вершин: a и c, c и d, d и e, b и e, d и f, множества вершин занесены в табл. 4. Не являются смежными, например, вершины а и d, а также b и d.
В графе G2 смежными являются следующие пары неориентированных рёбер: {a, c} и {c, d}, {b, e} и {d, e}, – а также тройка {c, d}, {d, e} и {d, f}.
Теорема. Сумма степеней вершин (n, m)-графа определяется как удвоенное число его рёбер:
Следствие теоремы. В любом неориентированном графе число вершин нечётной степени чётно (где V1и V2 – множества вершин нечётной и чётной степени соответственно.):
Упражнение.
Для неориентированного графа (примеры графов см. по ссылке https://zen.yandex.ru/media/independent_work/teoretikomnojestvennoe-predstavlenie-grafa-62735a02d5f97c19587d7738), соответствующего первой букве Вашего имени (или фамилии), запишите:
1) множество вершин, инцидентных ребрам g, ζ и ε;
2) множество рёбер, инцидентных вершинам a, d и f;
3) множество вершин, смежных с вершинами b, g и h;
4) множество рёбер, смежных с ребрами a, δ и θ;
5) определите степень вершин c, e и i;
6) множество изолированных вершин; множество концевых вершин.
