Матрицы ассоциировавшие с графами

Матриці асоційовані з графами.Матрицею суміжності поміченого графа порядку n називається квадратна бінарна матриця A порядку n, визначувана таким чином, : , де   Зауваження Якщо граф неорієнтований, то матриця його суміжності симетрична.Приклад Зауваження У випадку якщо в графі є кратні ребра і петлі, то елемент   матриці A дорівнюватиме числу дуг, що сполучають вершини i і j. При цьому неорієнтована петля вважається за два ребра.ПрикладНеорієнтований граф. Орієнтований граф. Зауваження Завдання графа за допомогою його матриці суміжності однозначне, якщо граф помічений. Більше того, будь-яка квадратна бінарна матриця є матрицею суміжності деякого орієнтованого графа. А довільна бінарна симетрична матриця - неорієнтованого графа.Визначення 2Ранг матриці суміжності графа G називається рангом графа G. Означають  .

 Література
1. Лекции по теории графов / Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. – М.: Наука, 1990.2. Зыков А.А. Основы теории графов. – М.: Наука, 1987.3. Татт У. Теория графов. – М.: Наука, 1988.4. Харари Ф. Теория графов. – М.: Мир, 1973.5. Березина Л.Ю. Графы и их применение. – М.: Просвещение, 1979.

Похожие работы