Спирина, М.С. Дискретная математика

*5 А г Рис. 2.1. Примеры графов: а — со смежными вершинами; б — полный; в — со смежными ребрами; г — с петлей линий X, соединяющее пару точек, — это некоторое подмноже­ ство множества V x V: X с (V x V). Точки называются вершинами, или узлами, графа, линии — ребрами графа. Примеры графов приведены на рис. 2.1. Пусть дан граф G - (V, X), где V = {V, W, ...} — конечное непустое множество его вершин, a X(V, W) — его ребра. Если ребро графа G соединяет две его вершины V и Ж (т.е. (V, W) е X), то говорят, что это ребро им инцидентно. Две вершины графа на­ зываются смежными, если существует инцидентное им ребро: на рис. 2.1 , а смежными являются вершины А и В, А и С. Если граф G имеет ребро Х( V, V), у которого начало и конец совпадают, то это ребро называется петлей. На рис. 2.1, г петля — q(C, С). Два ребра называются смежными, если они имеют общую вершину. На рис. 2.1, в смежными являются, например, ребра jcj и х2 с общей вершиной С. Граф G(V, X) может иметь ребра с одинаковыми парами вида X(V, W). Такие ребра называются кратными, или параллельными. На рис. 2.1, а кратными являются, например, ребра хх{А, В), х2(А, В). Вершинам А и В инцидентны ребра хи х2, х3. Количество одинако­ вых пар вида x(V, W) называется кратностью ребра ( К, W). На рис. 2.1, а ребро АС имеет кратность, равную 3, а ребро АВ — кратность, равную 2. Число ребер, инцидентных вершине А, на­ зывается степенью этой вершины и обозначается deg(A) (от англ. degree —степень). Если вершине инцидентна петля, она дает вклад в степень, равный двум, так как оба конца приходят в эту вершину. 70