Реферат Курсовая Конспект
Матрица инцидентности - раздел Математика, Матрица смежности Каждая Строка Соответствует Определённой Вершине Графа, А Столбцы Соответству...
|
Каждая строка соответствует определённой вершине графа, а столбцы соответствуют связям графа. В ячейку на пересечении i-ой строки с j-м столбцом матрицы записывается:
1 - в случае, если связь j «выходит» из вершины i,
−1 - если связь «входит» в вершину,
0 - во всех остальных случаях (т.е. если связь является петлёй или связь не инцидентна вершине)
Данный способ является самым ёмким и неудобным для хранения, но облегчает нахождение циклов в графе.
Список рёбер — это тип представления графа в памяти, подразумевающий, что каждое ребро представляется двумя числами — номерами вершин этого ребра. Список рёбер более удобен для реализации различных алгоритмов на графах по сравнению с матрицей смежности.
Обычно в теории графов выделяют некоторые разновидности графов. Среди таких разновидностей выделим следующие:
- полный граф - граф, матрица смежности которого состоит из одних единиц;
- полный обыкновенный граф - граф, у матрицы смежности которого все элементы, за исключением нулевых элементов главной диагонали, равны единице;
- пустой (нулевой) граф - граф, матрица смежности которого нулевая (обыкновенный граф, все вершины которого изолированы, т.е. нет ни одной пары смежных вершин);
- единичный граф - граф, матрица смежности которого единичная (граф, все вершины которого имеют петли и изолированы);
- плоский (планарный) граф - граф, который можно начертить на плоскости так, чтобы его ребра (дуги) пересекались только в его вершинах.
– Конец работы –
Эта тема принадлежит разделу:
Введение в теорию графов... Матрица смежности... Матрица инцидентности...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Матрица инцидентности
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Твитнуть |
Новости и инфо для студентов