ВУЗ:
Составители:
Рубрика:
20
В каждом ее столбце ровно две единицы, равный столбцов нет.
Рис. 25. Граф и его матрица смежности А и матрица инцидентности J.
Как и матрица смежности, матрица инцидентности определяет граф G с
точностью до изоморфизма.
Для ориентированных графов определение матрицы инцидентности J
видоизменяется:
J
kl
=
⎪
⎩
⎪
⎨
⎧
−
. ,0
, е ,1
, ,1
инцидентнынеедугаиkвершинаесли
едугиконцомявляетсяkвершинасли
едугиначаломявляетсяkвершинаесли
l
l
l
Рис. 26. Орграф и его матрица инцидентности.
Каждый столбец матрицы инцидентности содержит обязательно два
единичных элемента (для орграфа эти элементы всегда имеют различные знаки и
равны соответственно 1 и –1). Количество единиц в строке равно степени
соответствующей вершины (для орграфа количество положительных единиц
определяет положительную степень, а количество отрицательных единиц –
отрицательную степень). Нулевая
строка соответствует изолированной вершине, а
нулевой столбец – петле, при этом с какой вершиной эта петля связана, указаний
нет.
6. Деревья.
Существует простой и важный тип графов, называемых деревья. С одной
стороны, это достаточно просто устроенные графы, и многие задачи, сложные в
общей ситуации, легко решаются для деревьев. Доказано, например, что все деревья
реконструируемы; несложно распознается изоморфизм деревьев. С другой стороны,
деревья находят приложения в различных областях знания.
Деревом называется связный
граф, не содержащий циклов. Любой несвязный
граф без циклов называется ациклическим или лесом. Таким образом,
компонентами леса являются деревья. Удобно считать, что граф, состоящий из
одной изолированной вершины, тоже является деревом. Деревья считаются
Страницы
- « первая
- ‹ предыдущая
- …
- 18
- 19
- 20
- 21
- 22
- …
- следующая ›
- последняя »
