Инцидентность
Инцидентность — это отношение между вершиной и ребром: вершина инцидентна ребру, если это ребро соединяет данную вершину с другой вершиной или с ней самой. Иными словами, инцидентность показывает, какие рёбра «выходят» из каждой вершины.
Сначала важно различать сами объекты: вершина графа — точка или объект, а ребро графа — связь между двумя вершинами. Инцидентность описывает именно связь вершины с ребром, а не связь двух вершин между собой.
Как записывают инцидентность
Если ребро \(e\) соединяет вершины \(u\) и \(v\), это записывают так: \(e=uv\). Тогда ребро \(e\) инцидентно вершинам \(u\) и \(v\), а вершины \(u\) и \(v\) инцидентны ребру \(e\). В ориентированном графе у ребра различают начало и конец, но инцидентность всё равно означает принадлежность вершины этому ребру; направление дополнительно уточняет роль вершины.
Пусть граф содержит рёбра \(e_1=AB\) и \(e_2=BC\). Ребро \(e_1\) инцидентно вершинам \(A\) и \(B\), а ребро \(e_2\) — вершинам \(B\) и \(C\). Вершина \(B\) инцидентна обоим рёбрам \(e_1\) и \(e_2\).
Ребро \(xy\) инцидентно каким вершинам?
Инцидентность и смежность вершин — разные понятия. Вершины называют смежными, если их соединяет ребро. Вершина и ребро называют инцидентными, если вершина является концом этого ребра. Например, \(A\) и \(B\) смежны, а \(A\) и ребро \(AB\) инцидентны.
Инцидентность часто используют при составлении таблицы инцидентности: строки соответствуют вершинам, столбцы — рёбрам. В ячейке отмечают, принадлежит ли вершина данному ребру. Для неориентированного графа обычно ставят \(1\), если вершина и ребро инцидентны, и \(0\) — если нет.
Главное
- Инцидентность — связь вершины с ребром, имеющим эту вершину своим концом.
- Для ребра \(uv\) инцидентны вершины \(u\) и \(v\).
- Не путайте инцидентность вершины и ребра со смежностью двух вершин.