Студопедия — Орграфы и матрицы
Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Орграфы и матрицы






Матрицей смежностей А(D) орграфа D называется (р× р)-матрица ||aij||, у которой aij= 1, если ViVj- дуга орграфа D, и aij=0 в противном случае. Матрица смежностей которого имеет вид (рис. 6):

Рис. 6. Матрица смежности графа

Легко проверить, что суммы элементов по строкам матрицы A(D) равны полустепеням исхода вершин орграфа D, а суммы элементов по столбцам - полустепеням захода.

Как и в случае графов, степени матрицы смежностей А орграфа дают полную информацию о числе маршрутов, идущих из одной вершины в другую. Теорема. (i, j)-й элемент аijn матрицы А" равен числу маршрутов длины n, идущих из вершины vi в вершину vj.

Упомянем здесь вкратце еще о трех матрицах, связанных с орграфом Ds - о матрице достижимостей, матрице расстояний и матрице обходов. В матрице достижимостей R элемент rij равен 1, если вершина vi достижима из vj и равен 0 в противном случае. В матрице расстояний (i, j)-й элемент равен расстоянию из вершины vi в вершину vj; если же из vi в vj нет путей, то соответствующий элемент полагаем равным бесконечности. В матрице обходов (i, j)-й элемент равен длине наиболее длинного пути из vi в vj, а если таких путей нет, то опять-таки полагаем этот элемент равным бесконечности. Для орграфа D, показанного на рис. 7.

Рис. 7. Матрицы.

Следствие. Элементы матриц достижимостей и расстояний связаны со степенями матрицы А следующими соотношениями:

1) rii = 1 и dii = 0 для всех i;

2) rij = 1 тогда и только тогда, когда aijn> 0 для некоторого n;

3) d(vi, vj) равно наименьшему из чисел n, для которых aijn> 0

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

Поэлементное произведение В× С матриц B=||bij|| и C=||cij|| имеет своим (i, j)-м элементом bijcij. Матрицу достижимостей орграфа можно использовать для нахождения его сильных компонент.







Дата добавления: 2014-10-22; просмотров: 1595. Нарушение авторских прав; Мы поможем в написании вашей работы!



Расчетные и графические задания Равновесный объем - это объем, определяемый равенством спроса и предложения...

Кардиналистский и ординалистский подходы Кардиналистский (количественный подход) к анализу полезности основан на представлении о возможности измерения различных благ в условных единицах полезности...

Обзор компонентов Multisim Компоненты – это основа любой схемы, это все элементы, из которых она состоит. Multisim оперирует с двумя категориями...

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

Типовые примеры и методы их решения. Пример 2.5.1. На вклад начисляются сложные проценты: а) ежегодно; б) ежеквартально; в) ежемесячно Пример 2.5.1. На вклад начисляются сложные проценты: а) ежегодно; б) ежеквартально; в) ежемесячно. Какова должна быть годовая номинальная процентная ставка...

Выработка навыка зеркального письма (динамический стереотип) Цель работы: Проследить особенности образования любого навыка (динамического стереотипа) на примере выработки навыка зеркального письма...

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

Расчет концентрации титрованных растворов с помощью поправочного коэффициента При выполнении серийных анализов ГОСТ или ведомственная инструкция обычно предусматривают применение раствора заданной концентрации или заданного титра...

Психолого-педагогическая характеристика студенческой группы   Характеристика группы составляется по 407 группе очного отделения зооинженерного факультета, бакалавриата по направлению «Биология» РГАУ-МСХА имени К...

Общая и профессиональная культура педагога: сущность, специфика, взаимосвязь Педагогическая культура- часть общечеловеческих культуры, в которой запечатлил духовные и материальные ценности образования и воспитания, осуществляя образовательно-воспитательный процесс...

Studopedia.info - Студопедия - 2014-2024 год . (0.011 сек.) русская версия | украинская версия