рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

Матрица инцидентности

Матрица инцидентности - раздел Математика, Матрица смежности Каждая Строка Соответствует Определённой Вершине Графа, А Столбцы Соответству...

Каждая строка соответствует определённой вершине графа, а столбцы соответствуют связям графа. В ячейку на пересечении i-ой строки с j-м столбцом матрицы записывается:

1 - в случае, если связь j «выходит» из вершины i,

−1 - если связь «входит» в вершину,

0 - во всех остальных случаях (т.е. если связь является петлёй или связь не инцидентна вершине)

Данный способ является самым ёмким и неудобным для хранения, но облегчает нахождение циклов в графе.

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

Обычно в теории графов выделяют некоторые разновидности графов. Среди таких разновидностей выделим следующие:

- полный граф - граф, матрица смежности которого состоит из одних единиц;

- полный обыкновенный граф - граф, у матрицы смежности которого все элементы, за исключением нулевых элементов главной диагонали, равны единице;

- пустой (нулевой) граф - граф, матрица смежности которого нулевая (обыкновенный граф, все вершины которого изолированы, т.е. нет ни одной пары смежных вершин);

- единичный граф - граф, матрица смежности которого единичная (граф, все вершины которого имеют петли и изолированы);

- плоский (планарный) граф - граф, который можно начертить на плоскости так, чтобы его ребра (дуги) пересекались только в его вершинах.

– Конец работы –

Эта тема принадлежит разделу:

Матрица смежности

Введение в теорию графов... Матрица смежности... Матрица инцидентности...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Матрица инцидентности

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

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

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги