20503

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

Доклад

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

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

Украинкский

2013-07-25

28 KB

32 чел.

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

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

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

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


 

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

24299. Мировые тенденции развития современной журналистики 48 KB
  С другой стороны все более заметным становится рост общественной активности в информационной сфере проявляющийся в создании альтернативных массмедиа по преимуществу на сетевой платформе а также в деятельности гражданских организаций мониторинга СМИ и медиакритики в отстаивании требований демократизации медийного сектора сохранения и развития мощных общественных средств массовой информации. В большой Европе СМИ все чаще называют медиаиндустрией а журналистские произведения медиапродуктами рассматривая их как товарную продукцию...
24300. Публицистические жанры журналистики и их место в системе жанров журналистского творчества 51 KB
  Жанры журналистики отличаются от литературных достоверностью адресностью фактов. Жанр в прессе это способ подачи информации. Теоретики классифицируют жанры по назначению объекту изображения теме стилистике выразительным средствам и проч.
24301. Этика в СМИ, теория свободы прессы 24 KB
  Этика в СМИ теория свободы прессы. Главная тенденция по итогам исследования 2010 года СМИ в теме социальной ответственности низкая доля внимания средств массовой информации к тематике в целом. встречаются редко и лишь на страницах отдельных СМИ. Причем если деятельность официально зарегистрированных организаций благотворительных и правозащитных объединений фондов помощи и общественных ассоциаций проводящих мероприятия имеющие статус официальных а также отдельные социальные акции крупных компаний или государственных структур еще...
24302. Состояние и развитие рекламного рынка в России и мире. Законодательное регулирование рекламных процессов 37 KB
  История рекламы исчисляется не годами а тысячелетиями. С момента возникновения такой экономической категории как товар и установления товарного производства началось развитие рекламы как искусства. Журнал Лаборатория рекламы маркетинга и PR №1. Мировой рекламный рынок: рынок мировой рекламы растет однако его рост замедлился.
24303. Планирование рекламной кампании 31.5 KB
  Планирование рекламной кампании. Планирование рекламной кампании разбивается на следующие этапы: Определение целей рекламной кампании; Разработка рекламной идеи и стратегии рекламной кампании; Исследование рынка; Разработка бюджета рекламной кампании; Выбор средств распространения рекламной информации; Выбор графика проведения рекламной кампании; Составление медиаплана рекламной кампании; Оценка эффективности рекламной кампании. Рекламные кампании различаются: По основному объекту рекламирования можно выделить кампании по рекламе:...
24304. Виды и формы рекламной информации и средств рекламы 30 KB
  ATL это мероприятия по размещению прямой рекламы которые задействуют 6 основных носителей ТВ пресса радио реклама на транспорте наружная реклама реклама в Интернет. Наружная реклама рекламные средства в виде вывесок наружных плакатов щитов перетяжек витрин козырьков световых установок на зданиях улицах и обочинах дороги. Наружная реклама содержит и использует лаконичный запоминающийся текст рисунок. Реклама на транспорте разновидность рекламы достигающей людей которые пользуются общественным транспортом.
24305. Оценка эффективности рекламной кампании 26.5 KB
  По этой причине оценка эффективности рекламы учитывает комплекс создавшихся на рынке условий и факторов способствующих или препятствующих решению маркетинговых задач. Основная задача исследований эффективности рекламы состоит в том чтобы научиться косвенно предсказывать ее влияние на коммерческую деятельность фирмы. Эти исследования прежде всего направлены на повышение эффективности рекламной деятельности снижения риска ее проведения лучшее использование финансовых средств.
24306. Правовой режим предвыборки, ответственность за нарушение законодательства 40.5 KB
  Владимир Евстафьев рассказал вицепрезидент Ассоциации коммуникационных агентств России академик рекламы Агитация предвыборная предвыборная агитация деятельность осуществляемая в период избирательной кампании и имеющая целью побудить или побуждающая избирателей к голосованию за кандидата кандидатов список кандидатов или против него них. Предвыборная агитация может принимать следующие формы: а призывы голосовать за или против кандидата списка кандидатов; б выражение предпочтения какомулибо кандидату избирательному...
24307. Защита репутации юридическими средствами 87.5 KB
  Защита репутации юридическими средствами Защита чести достоинства и деловой репутации Гражданин вправе требовать по суду опровержения порочащих его честь достоинство или деловую репутацию сведений если распространивший такие сведения не докажет что они соответствуют действительности. Правила настоящей статьи о защите деловой репутации гражданина соответственно применяются к защите деловой репутации юридического лица. Защита репутации: право и PR Репутация это информационное по сути явление которое отчасти пытаются описать и защитить с...