Смежность, инцидентность, степени

Если в графе имеется ребро , то говорят, что вершины и смежны в этом графе, ребро инцидентно каждой из вершин , , а каждая из них инцидентна этому ребру.

Множество всех вершин графа, смежных с данной вершиной , называется окрестностью этой вершины и обозначается через .

На практике удобным и эффективным при решении многих задач способом задания графа являются так называемые списки смежности. Эти списки могут быть реализованы различными способами в виде конкретных структур данных, но в любом случае речь идет о том, что для каждой вершины перечисляются все смежные с ней вершины, т.е. элементы множества . Такой способ задания дает возможность быстрого просмотра окрестности вершины.

Число вершин, смежных с вершиной , называется степенью вершины и обозначается через .

Если сложить степени всех вершин некоторого графа, то каждое ребро внесет в эту сумму вклад, равный 2, поэтому справедливо следующее утверждение:

Теорема 2. .

Это равенство известно как "лемма о рукопожатиях". Из него следует, что число вершин нечетной степени в любом графе четно.

Вершину степени называют изолированной.

Граф называют регулярным степени , если степень каждой его вершины равна .

Набор степеней графа - это последовательность степеней его вершин, выписанных в неубывающем порядке.

18.

Не нашли, что искали? Воспользуйтесь поиском: