Головна

матриця інцидентності

  1. SWOT- матриця
  2. А) Квадратна матриця і її визначник. б) Особлива і неособлива квадратні матриці. в) Приєднана матриця. г) Матриця, зворотна даної, і алгоритм її обчислення.
  3. А) Поняття матриці. б) Види матриці. в) Транспонування матриці. г) Рівність матриць. д) Алгебраїчні операції над матрицями: множення на число, додавання, множення матриць.
  4. ДЗ-3. Ранг матриці. Зворотна матриця. Спільність систем лінійних рівнянь
  5. інформаційна матриця
  6. інформаційна матриця
  7. інформаційна матриця

Кожен рядок відповідає певній вершині графа, а стовпці відповідають зв'язкам графа. У осередок на перетині i-го рядка з j-м стовпцем матриці записується:

1 - В разі, якщо зв'язок j «виходить» з вершини i,

-1 - Якщо зв'язок «входить» в вершину,

0 - У всіх інших випадках (т. Е. Якщо зв'язок є петлею або зв'язок не инцидентна вершині)

Даний спосіб є найбільш ємним і незручним для зберігання, але полегшує знаходження циклів в графі.

список ребер - Це тип представлення графа в пам'яті, що має на увазі, що кожне ребро представляється двома числами - номерами вершин цього ребра. Список ребер більш зручний для реалізації різних алгоритмів на графах порівняно з матрицею суміжності.

Зазвичай в теорії графів виділяють деякі різновиди графів. Серед таких різновидів виділимо наступні:

- повний граф - Граф, матриця суміжності якого складається з одних одиниць;

- повний звичайний граф - Граф, у матриці суміжності якого всі елементи, за винятком нульових елементів головної діагоналі, дорівнюють одиниці;

- порожній (нульовий) граф - Граф, матриця суміжності якого нульова (звичайний граф, всі вершини якого ізольовані, т. Е. Немає жодної пари суміжних вершин);

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

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



Лекція 21: Введення в теорію графів. Способи подання орієнтованих і неорієнтованих графів: матриці суміжності і інцидентності, списки Інцидентне. | Маршрути і зв'язність
© um.co.ua - учбові матеріали та реферати