.RU

§ 6.1: Определение графа. Ориентированные и неориентированные графы - Приднестровский государственный университет...


^ § 6.1: Определение графа. Ориентированные и неориентированные графы

Определение 6.1: Совокупность двух множеств - точек и линий, между элементами которых определено отношение инцидентности, называется графом G=, причем каждый элемент еЕ инцидентен не более чем двум элементам v1, v2 V.

При этом элементы множества V называются вершинами графа, а элементы множества Е - ребрами графа. И вершины и ребра являются элементами графа, и правомерна запись: vG eG.

Синонимом понятия инцидентность является принадлежность. Ребро инцидентно не более чем двум вершинам.

Две вершины называются смежными, если они инцидентны одному и тому же ребру, два ребра называются смежными, если они имеют общую инцидентную вершину.

Напомним, что бинарным отношением , определенным на множестве V, является подмножество его прямого произведения  V2=VV.

Элементы vi,vjV находятся в отношении , если пара (vi,vj) .

^ Определение 6.2 (2-ое определение графа): Совокупность множества V с заданным на нем бинарным отношением  называется графом G=, где множество вершин V называется носителем графа, а множество ребер  - сигнатурой графа.

В некоторых задачах инцидентные ребру вершины не равноправны, а рассматриваются в определенном порядке. Тогда каждому ребру можно приписать направление от первой вершины ко второй. Конец такого ребра помечается стрелкой.

Направленные ребра называются дугами, а содержащий их граф – ориентированным или оргафом. Рассмотренный ранее граф - не ориентирован. Будем называть его просто графом.

В дальнейшем неориентированный граф (или просто граф) будем обозначить G=, его ребра – {vi,vj}, а ориентированный – D, его ребра – (vi,vj).

Граф, содержащий и ребра, и дуги, называются смешанным.

Примеры графов: неориентированные графы (Рис. 6.1)

а) Если каждая вершина графа соединена ребром с каждой из оставшихся вершин, то такой граф называется полным и обозначается КI V I . Для примера а) - К4

б) Несколько различных ребер могут быть инцидентны одной и той же паре вершин. В этом случае, они называются кратными ребрами. Граф, содержащий кратные ребра, называется мультиграфом.





Граф, содержащий кратные ребра и петли, называется псевдографом.

в) Ребро может быть инцидентно одной вершине, т.е. соединять ее саму с собой. Такое ребро называют петлей. Граф без петель и кратных ребер называют простым.

г) Множество ребер Е может быть пустым. Если же и множество вершин V пусто, то E тем более пусто. Граф, состоящий из единственной вершины, называют тривиальным.

д) Если множество вершин V простого графа допускает разбиение на два подмножества V1,V2V (V1  V2=V, V1  V2=) и не существует ребер, соединяющих вершины из одного и того же подмножества, то граф называется двудольным или биграфом и обозначается

Пример: Пусть V = {v1,v2,v3,v4,v5} (рис.6.1. д)

V1 = {v1, v4}, V2 = {v2,v3,v5}, I V1 I =2 , I V2 I =3





Ориентированные графы (рис.6.2): б), в) Как и неориентированный, орграф может иметь кратные ребра - дуги. В этом случае дуги называются параллельными. Параллельные дуги, одинаково направленные по отношению к некоторой вершине, называются строго параллельными.

е) Определение ориентированного биграфа аналогично, но необходимо учесть, что начало каждой дуги принадлежит множеству V1, а конец - множеству V2.

^ § 6.2: Способы задания графов

Пусть задан граф G = , I V I = n, I E I = m. Тогда граф можно задать в виде :

1) в виде матрицы смежности U размером n  n, где каждый элемент матрицы ui,j равен количеству ребер, инцидентных вершинам v i и v j.

2) в виде матрицы инцидентности W размером m  n, где

а) для неориентированного графа G = каждый элемент wij



б) для ориентирования D = графа



Если ei является петлей при вершине vj , то элемент wi,j равен любому числу, отличному от 1, -1 и 0.

Матрица смежности неориентированного графа симметрично относительно главной диагонали. Матрица ориентированного графа - не симметрична.

Пример. Рассмотрим два графа - неориентированный и ориентированный (рис. 6.3, 6.4). Зададим их матрицами смежности и инцидентности.



Матрицы смежности и инцидентности неориентированного графа:




v1

v2

v3

v4

v5

v6

v7







v1

v2

v3

v4

v5

v6

v7

v1

0

1

1

0

1

0

0

e1

1

1

0

0

0

0

0

v2

1

0

0

1

0

1

0

e2

1

0

1

0

0

0

0

v3

1

0

0

1

1

0

0

e3

0

1

0

1

0

0

0

v4

0

1

1

0

0

1

0

e4

1

0

0

0

1

0

0

v5

1

0

1

0

0

0

1

e5

0

1

0

0

0

1

0

v6

0

1

0

1

0

0

1

e6

0

0

1

1

0

0

0

v7

0

0

0

0

1

1

0

e7

0

0

1

0

1

0

0




e8

0

0

0

1

0

1

0

e9

0

0

0

0

1

0

1

e10

0

0

0

0

0

1

1


Матрицы смежности и инцидентности ориентированного графа:




v1

v2

v3

v4

v5

v6

v7







v1

v2

v3

v4

v5

v6

v7

v1

0

1

1

0

0

0

0

e1

-1

1

0

0

0

0

0

v2

0

0

0

1

0

0

0

e2

-1

0

1

0

0

0

0

v3

0

0

0

0

1

1

1

e3

0

-1

0

1

0

0

0

v4

0

0

0

0

0

0

0

e4

0

0

-1

0

1

0

0

v5

0

0

0

0

0

0

0

e5

0

0

-1

0

0

1

0

v6

0

0

0

0

0

0

0

e6

0

0

-1

0

0

0

1

v7

0

0

0

0

0

0

1

e7

0

0

0

0

0

0

3


3) Граф может быть задан списком ребер.

Таким образом, графы могут быть заданы различными способами.




Иногда сложно понять, одинаковы ли графы, изображенные разными чертежами.

Вид матриц графа зависит от нумерации вершин и ребер графа.

Строго говоря, граф считается полностью заданным, если нумерация его вершин зафиксирована.

Графы, отличающиеся только нумерацией вершин, называются изоморфными (Рис.6.5).

Перенумерация вершин графа задается строкой 1,...,..,...,.n новых номеров вершин, расположенных в исходном порядке.


119--opdf05-gosudarstvennij-obrazovatelnij-standart-visshego-professionalnogo-obrazovaniya.html
11analiz-gosudarstvennoj-avtomatizirovannoj-sistemi-rossijskoj-federacii-vibori.html
11pereklyuchatel-vida-topliva-gaz-benzin-sovmeshyonnij-s-ukazatelem-urovnyadavleniya-gaza-i-indikatorami-utechki-ep0802.html
12-14-aprelya-v-kronshtadtskom-dvorce-molodezhi-sovetskaya-ul-35-projdet-vtoroj-mezhdunarodnij-forum-kronshtadt-2025-i-molodezh.html
12-af-losev-i-nemeckaya-filosofskaya-tradiciya-i-i-polzunova-bijskij-tehnologicheskij-institut-filial-yu-v.html
12-byudzhetnoe-nalogovoe-finansovoe-zakonodatelstvo-i-voprosi-ekonomicheskoj-politiki.html
  • predmet.bystrickaya.ru/rezultati-sorevnovanij-doklad-mou-sosh-1-im-a-p-gajdara.html
  • klass.bystrickaya.ru/anitama-sinis-lgs-ou-ornini-blanksnde-basiladi-shiu-n-kn-20-zh.html
  • knigi.bystrickaya.ru/smena-professii-reportyor-professionalizm-i-etika.html
  • writing.bystrickaya.ru/ekologchn-katastrofi-nashogo-chasu.html
  • studies.bystrickaya.ru/biznes-plan-planirovanie-finansovo-ekonomicheskoj-deyatelnosti-predpriyatiya-xxxxxx-po-proizvodstvu-novoj-produkcii-chast-16.html
  • prepodavatel.bystrickaya.ru/taliya-i-bedra-ostavatsya-v-dvizhenii-kak-viglyadyat-nashi-tela-kakovi-prichini-togo-chto-mi-viglyadim-tak-a-ne-inache.html
  • klass.bystrickaya.ru/analiz-otechestvennogo-opita-strategicheskogo-planirovaniya-razvitiya-korporacii-analiz-opita-strategicheskogo-korporativnogo-planirovaniya.html
  • apprentice.bystrickaya.ru/v-d-nogin-sankt-peterburgskij-gosudarstvennij-tehnicheskij-universitet.html
  • zadachi.bystrickaya.ru/politicheskaya-kultura-smisl-i-metodologicheskoe-znachenie-kategorii-chast-10.html
  • thesis.bystrickaya.ru/pravopisanie-pristavok-uchebniku-russkij-yazik-6-klass-avtori-s-i-lvova-v-v-lvov-kniga-dlya-uchashihsya.html
  • tests.bystrickaya.ru/lekciya-elektromagnitnie-volni.html
  • predmet.bystrickaya.ru/sabati-tairibi-zhmba-ajtis-sabati-masati-blmdlk-nrzhan-men-saparali-ajtisi-men-tanisu.html
  • zadachi.bystrickaya.ru/opredelenie-gorizontalnoj-sostavlyayushej-magnitnogo-polya-zemli.html
  • znanie.bystrickaya.ru/6-vospitatelnaya-rabota-shkoli-publichnij-doklad.html
  • literature.bystrickaya.ru/dni-rozhdeniya-moskovskij-komsomolec-avtor-ne-ukazan-01072008-139-str-12.html
  • tasks.bystrickaya.ru/1-stanovlenie-sektora-ngo-v-kontekste-processa-demokratizacii-v-ukraine.html
  • predmet.bystrickaya.ru/reshenie-po-zhilim-domam-nesnosimih-serij-budet-prinimatsya-v-ramkah-gosudarstvennoj-programmi-zhilishe-gosudarstvennaya-programma-goroda-moskvi-na-2012-2016-gg-zhilishe-vklyuchaet-rya.html
  • shpora.bystrickaya.ru/zashita-besprovodnih-setej.html
  • znanie.bystrickaya.ru/a-a-lyapunov-monografiya-posvyashena-razvitiyu-i-sistematicheskomu-izlozheniyu-osnov-obshej-teorii-organizacii-oto.html
  • college.bystrickaya.ru/10-12-fevralya-2012-goda-zagorodnij-otel-chajka-nizhegorodskaya-oblast-pos-zhelnino.html
  • znaniya.bystrickaya.ru/programma-tura-29-dekabrya-vstrecha-v-holle-vibrannoj-gostinici-avtobusnaya-ekskursiya-velikie-monastiri-moskvi.html
  • notebook.bystrickaya.ru/itar-tass-vedushie-predpriyatiya-urala-i-zapadnoj-sibiri-predstavili-svoj-investicionnij-potencial-delovim-krugam-katara-04102010.html
  • pisat.bystrickaya.ru/tema-24-programmirovanie-algoritmov-s-podprogrammami-uchebno-metodicheskij-kompleks-institut-sistemnogo-analiza.html
  • obrazovanie.bystrickaya.ru/prikaz-11-maya-2007-g-n-327-ob-utverzhdenii-standarta-medicinskoj-pomoshi-bolnim-s-hronicheskoj-obstruktivnoj-boleznyu-legkih-pri-okazanii-specializirovannoj-pomoshi.html
  • thesis.bystrickaya.ru/postanovlenie-o-vnesenii-izmenenij-i-dopolnenij-v-reshenie-xv-zasedaniya-soveta-municipalnogo-rajona-sosnogorsk.html
  • urok.bystrickaya.ru/programma-disciplini-socialnaya-psihologiya-dlya-napravleniya-030100-62-filosofiya-podgotovki-bakalavra-avtor-v-p-poznyakov.html
  • occupation.bystrickaya.ru/ob-attestacii-pedagogicheskih-i-rukovodyashih-rabotnikov-gosudarstvennih-i-municipalnih-obrazovatelnih-uchrezhdenij-na-pervuyu-i-vtoruyu-kvalifikacionnie-kategorii-v-2008-2009-uchebnom-godu-stranica-5.html
  • klass.bystrickaya.ru/7-blank-k-metodike-ocenka-potrebnosti-v-dostizhenii-uchebno-metodicheskij-kompleks-disciplini-praktikum-po-proforientacii.html
  • knigi.bystrickaya.ru/rezistornij-kaskad-predvaritelnogo-usileniya-na-bipolyarnom-tranzistore.html
  • shkola.bystrickaya.ru/rabota-s-veteranami-semejnij-dosug-turizm.html
  • kolledzh.bystrickaya.ru/algoritm-forda-falkersona-aff.html
  • klass.bystrickaya.ru/a-a-bova-i-dr-mn-bgmu-2005-276-s-stranica-9.html
  • report.bystrickaya.ru/instrukciya-dlya-uchastnika-tendera-1-stranica-3.html
  • laboratornaya.bystrickaya.ru/rabochaya-programma-po-discipline-pablik-rilejshnz-po-specialnosti-032401-65-reklama.html
  • nauka.bystrickaya.ru/v-i-petrov-poselenie-rp-zavetnoe.html
  • © bystrickaya.ru
    Мобильный рефератник - для мобильных людей.