Дискретна математика, лекція 23-2: орієнтовані графи

Розглянуто такі питання:
-- поняття орієнтованого графу (орграфу), перевизначення пов'язаних понять;
-- лема про рукостискання для орграфів;
-- способи представлення орграфів: матриця суміжності, матриця інцидентності, списки суміжності;
-- сильна та слабка зв'язність орграфів, компоненти сильної зв'язності.
Лектор: Сергій Яковлєв.
Дивіться у 720p, оскільки написи на дошці доволі дрібні.

[@matviikistaiev6790]

22:28 здається ж -1, якщо виходить з вершини, та +1, якщо входить?)

[@MMIS_IPT]

Ніт) Ті, що виходять, зберігають властивості неорієнтованих аналогів, зокрема, структуру списків суміжності. Тому для ребер, які виходять, залишається +1, а для тих, що входять, змінюємо на -1.

[@d4z3r1tap4]

А якщо петля, то 2 у орграфі матриці інцидентності?

[@MMIS_IPT]

Нема уніфікованого підходу Іноді зручно нуль (ребро вийшло, ребро увійшло), іноді зручно один (є шлях з вершини у вершину), іноді - два (умовна степінь зв'язності)