Студопедия
Новини освіти і науки:
МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах


РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання


ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ"


ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ


Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків


Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні


Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах


Гендерна антидискримінаційна експертиза може зробити нас моральними рабами


ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ


ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів



Інцидентність

 

Інцидентність уявляє відношення між різнорідними елементами графа – вершинами і ребрами: якщо вершина є кінцем ребра ek, то вона інцидентна ребру ek, а ребро ek інцидентне вершині .

В орграфах розрізняють позитивну інцидентність (дуга виходить з вершини) та негативну інциденність (дуга заходить у вершину).

Відношення інцидентності дозволяє представить - граф у вигляді матриці інцидентності розміру , в якій рядки відповідають вершинам, а стовпці – ребрам (дугам) графа.

Кожен елемент матриці визначається наступним чином:

а) для неорієнтованого графа дорівнює:

1) 1, якщо вершина інцидентна ребру ;

2) 0, якщо та не інцидентні;

б) для орграфа дорівнює:

1) 1, якщо - початкова вершина, тобто позитивна інцидентність;

2) -1, якщо - кінцева вершина, тобто негативна інцидентність;

3) 0 – як у пункті а).

Матриці інцидентності псевдографа А1 (рис. 8.4, а) та орграфа А2 (рис. 8.3) наведені відповідно на рис. 8.6.

Рис. 8.6 Матриці інцидентності графів

 

Властивості матриць інцидентності. Кожен стовпець матриці інцидентності містить обов’язково два одиничних елемента, а для орграфа ці елементи мають різні знаки і відповідно дорівнюють 1 та -1.

Для неорієнтованого графа кількість одиниць в рядку дорівнює ступеню вершини.

Для орграфа сума позитивних елементів дорівнює позитивному ступеню вершин, сума негативних – негативному ступеню.

Нульовий рядок відповідає ізольованій вершині.

Нульовий стовпець відповідає петлі, при цьому матриця не надає інформації про те, з якою вершиною пов’язана петля.

 




Переглядів: 2956

<== попередня сторінка | наступна сторінка ==>
Суміжність у графах | Інші властивості та різновиди графів

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

  

© studopedia.com.ua При використанні або копіюванні матеріалів пряме посилання на сайт обов'язкове.


Генерація сторінки за: 0.002 сек.