20503

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

Доклад

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

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

Украинкский

2013-07-25

28 KB

31 чел.

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

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

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

Матриця суміжності графа 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: якщо між  і  немає ребра.


 

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

15088. Ортағасырлық Түркі ғалымдары мен жазушылары 57 KB
  ӘӨЖ 951/959 ОРТАҒАСЫРЛЫҚ ТҮРКІ ҒАЛЫМДАРЫ МЕН ЖАЗУШЫЛАРЫ Ф.М. Махашова №36 қазақ орта мектебі Тараз қ. Ғалымдар Қайта өрлеу дәуірін Ренессанс деп атайды өйткені бұл кезеңде антикалық дәстүрлер қайта жаңғырып ғылым мен мәдениетте әдебиетте өрлеу өркендеу ба...
15089. Өлең аудармасының теориясы мен поэтикасы 264.5 KB
  Адамзат аударма арқылы араласып-құраласады. Біз өмір сүріп жатқан әлемнің іштей белгілі бір жүйеге құрылғандығы, адам тіршілігінің кез келген қимыл-қарекеті өзінше шағын жүйе екендігі, онсыз әлемнің тұтас жүйесі жасалмайтындығы белгілі.
15090. Өлеңге тоқтамайды Шал дегенің 60 KB
  ӨЛЕҢГЕ ТОҚТАМАЙДЫ ШАЛ ДЕГЕНIҢ Шал ақын аталып кеткен Тiлеуке Құлекеұлы қазiргi Ақмола облысы жерiнде Азат темiр жол станциясының маңында 1748 жылы дүниеге келген. Әкесi Құлеке қазаққалмақ соғысының атақты батырларының бiрi. Анасы атақты Төле бидiң қызы. Құлеке мен оның а
15091. Пушкин және Қазақ әдебиеті 357 KB
  Әрбір ұлт әдебиетінің тарихында туған халқының мәдени өмірінде жеке өзі бір кезең – дәуірді түзеп, соңына ұмытылмас, өшпес із-мұра қалдыратын заңғар суреткерлер болады. Сондай тұлға, әлем әдебиетіндегі аса ғажайып орыс ақыны
15092. СҰЛТАНМАХМҰТ ТОРАЙҒЫРОВ РОМАНДАРЫНДАҒЫ ОБРАЗДАР ЖҮЙЕСІ 55 KB
  СҰЛТАНМАХМҰТ ТОРАЙҒЫРОВ РОМАНДАРЫНДАҒЫ ОБРАЗДАР ЖҮЙЕСІ М. Абизенова М.Х Коржумбаева Б.Ахметов атындағы Павлодар педагогикалық коледжі Павлодар қ. Кейіпкерлердің тілдік мінездемесін бір бірімен салыстыра талдау табиғат суретін кейіпкерлер портретін жа
15093. Сәбит Мұқановтың поэзиясы 45 KB
  Сәбит Мұқанов 1900-1973 Сәбит Мұқанов қазақтың әйгілі жазушысы қазақ әдебиетінің көрнекті қайраткері Қазақ КСР Ғылым академиясының академигі. Оның есімін жалпы қазақ оқырманына кеңінен танытқан Сұлушаш дастаны Адасқандар романы осы кезде өмірге келді. Осыларғ...
15094. Сәкен Сейфуллиннің Көкшетау поэмасын оқыту 36 KB
  Сәкен Сейфуллиннің Көкшетау поэмасын оқыту Ғ.А. Қазанбаева №136 орта мектеп Алматы қаласы Тақырыбы: Сәкен Сейфуллин. Көкшетау поэмасының мазмұны мен идеясы. Мақсаты: а білімділік: Поэманың мазмұнын қайталай отырып жазылу тарихына көтерге...
15095. Сәкен Сейфуллиннің поэзиясы 62.5 KB
  Жаңа тұрмыс жырлары Сәкен Сейфуллинннің поэзиясы Жиырмасыншы жылдары қоғамдық өмірде болған түбегейлі өзгерістер жаңа заман дамуының қарқындылығы тарихи оқиғалардың жедел ауысып отыруы Сәкен поэзиясында сол дәуір бейнесін берерлік екінші образ жүйрік пойыз...
15096. Түркі халықтарының жазба ескерткіші және оның көздері 70.5 KB
  ТҮРКІ ХАЛЫҚТАРЫНЫҢ ЖАЗБА ЕСКЕРТКІШІ ЖӘНЕ ОНЫҢ КӨЗДЕРІ С. Тәжіғұлова Ғ. Мұратбаев атындағы № 17 орта мектеп Тараз қ. Әрбір дәуірдің елеулі кезеңді оқиғаларын заманының белгілі ақынжазушылары дастанжырларға ойшылдары тарихшежіреге айналдыры