20503

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

Доклад

Информатика, кибернетика и программирование

Матриця суміжності графа G зі скінченною кількістю вершин n пронумерованих числами від 1 до n це квадратна матриця A розміру n в якій значення елементу aij рівне числу ребер з iї вершини графа в jу вершину. Матриця суміжності простого графа що не містить петель і кратних ребер є бінарною матрицею і містить нулі на головній діагоналі. Матриця суміжності неорієнтованого графа симетрична а значить володіє дійсними власними значеннями і ортогональним базисом з власних векторів.

Украинкский

2013-07-25

28 KB

22 чел.

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

Матриця суміжності

Матриця суміжності — один із способів представлення графа у вигляді матриці.

Матриця суміжності графа G зі скінченною кількістю вершин n (пронумерованих числами від 1 до n) — це квадратна матриця A розміру n, в якій значення елементу aij рівне числу ребер з i-ї вершини графа в j-у вершину.

Іноді, особливо у разі неорієнтованого графа, петля (ребро з i-ї вершини в саму себе) вважається за два ребра, тобто значення діагонального елементу aii в цьому випадку рівне подвоєному числу петель навколо i-ї вершини.

Матриця суміжності простого графа (що не містить петель і кратних ребер) є бінарною матрицею і містить нулі на головній діагоналі.

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

Два графи G1 і G2 з матрицями суміжності A1 і A2 є ізоморфними якщо і тільки якщо існує матриця перестановок P, така що PA1P-1 = A2.

З цього випливає, що матриці A1 і A2 подібні, а значить мають рівні набори власних значень, визначників і характеристичні многочлени. Проте зворотне твердження не завжди вірне — два графи з подібними матрицями суміжності можуть бути неізоморфними.

Матриця суміжності і списки суміжності є основними структурами даних, що використовуються для представлення графів в комп'ютерних програмах.

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

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

Ма́триця інциде́нтності — одна з форм представлення графа, в якій вказуються зв'язок між інцидентними елементами графа (ребро (дуга) і вершина). Стовпці матриці відповідають ребрам, рядки — вершин. Ненульове значення у клітинці матриці вказує на зв'язок між вершиною і ребром (їх інцедентність).

Кожна комірка матриці може набувати трьох значень:

1: якщо ребро виходить з  і входить у ;

-1: якщо ребро входить у  і виходить з ;

0: якщо між  і  немає ребра.


 

А также другие работы, которые могут Вас заинтересовать

76572. Виды договоров 18.7 KB
  Предварительный договор это соглашение сторон о заключении основного договора в будущем на условиях предусмотренных предварительным договором п. Его нужно отличать от срочного договора заключенного под отлагательным сроком когда права и обязанности сторон возникают не сразу при заключении договора а по истечении определенного срока. Предварительный договор представляет собой добровольно принятое сторонами обязательство заключить дополнительно основной договор в нем должны быть согласованы все существенные условия основного договора....
76573. Понятие и содержание договора 28.41 KB
  Понятие договора дано в статье 420 ГК РФ. Для договора необходимо совпадение воли сторон по всем вопросам имеющим для них существенное значение. Правовое регулирование договора как сделки осуществляется также правилами главы 9 ГК РФ о двух и многосторонних сделках.
76577. Обеспечение исполнения обязательств 35.91 KB
  Такие правовые средства называются способами обеспечения исполнения обязательства. Использование сторонами обеспечения обязательства с одной стороны стимулирует самого должника к надлежащему исполнению обязательства с другой стороны гарантирует удовлетворение интересов кредитора в случае неисполнения или ненадлежащего исполнения обязательства. Обеспечение обязательства по общему правилу осуществляется на основании соглашения сторон.
76578. Условия исполнения обязательств 18.43 KB
  Условия исполнения обязательств К условиям характеризующим надлежащее исполнение обязательства относятся требования предъявляемые к субъекту и предмету исполнения а также к сроку месту и способу исполнения. Такие условия обычно закрепляются диспозитивными нормами закона что дает возможность его участникам избрать конкретный вариант исполнения обязательства в наибольшей степени отвечающий их интересам. Субъектом исполнения обязательства является должник. Обычно предполагается что он сам исполняет лежащий на нем долг что является...
76579. Понятие и основные начала исполнения обязательств 28.03 KB
  Посредством исполнения обязательства происходит реальное удовлетворение интересов управомоченного лица ради которого оно и вступило в данное обязательство. Статья 310 ГК РФ закрепляет недопустимость одностороннего отказа от исполнения обязательства и одностороннего изменения его условий. Для обязательств связанных с осуществлением сторонами предпринимательской деятельности основания для одностороннего отказа могут быть предусмотрены не только законом но и договором если иное не вытекает из закона или существа обязательства.
76580. Перемена лиц в обязательстве 35.07 KB
  Исключение составляют случаи когда права неразрывно связаны с личностью кредитора в частности требования об алиментах о возмещении вреда причиненного жизни или здоровью. Кроме того уступка требования может быть прямо запрещена законом или договором например согласно пункту 5 ст. Сделка которая служит основанием для перехода прав кредитора называется уступкой требования или цессией. Уступка требования по ордерной ценной бумаге совершается путем индоссамента на этой ценной бумаге.