.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
  • literature.bystrickaya.ru/bobrovnikovo.html
  • pisat.bystrickaya.ru/spravka-ob-itogah-rassmotreniya-krasnogorskim-rajonnim-sudom-g-kamenska-uralskogo-sverdlovskoj-oblasti-ugolovnih-del-i-materialov-v-otnoshenii-nesovershennoletnih-za-2011-god.html
  • grade.bystrickaya.ru/monografiya-posvyashena-aktualnim-voprosam-primeneniya-kraniomet.html
  • uchebnik.bystrickaya.ru/v-naukah-o-cheloveke-dolzhen-proizojti-sdvig-kotorij-mozhno-sravnit-lish-s-kopernikianskoj-revolyuciej-v-astronomii.html
  • uchebnik.bystrickaya.ru/v-i-goncharov-adres-redakcii-stranica-4.html
  • shpargalka.bystrickaya.ru/vlastelin-kolec-vozvrashenie-korolya-stranica-3.html
  • tasks.bystrickaya.ru/20-harakteristika-sovremennogo-nauchnogo-metoda-1-uchenie-konfuciya.html
  • write.bystrickaya.ru/glava-xv-88-o-chestvovanii-svyatih-i-ih-moshej-kniga-pervaya-29.html
  • vospitanie.bystrickaya.ru/zadachi-razvitie-prostranstvennih-predstavlenij-detej-razvitie-rechi-obogashenie-aktivnogo-slovarya-razvitie-proizvolnoj-pamyati.html
  • esse.bystrickaya.ru/put-razmesheniya-na-sajte-mintrud-rtsocialnoe-partnerstvorazvitie-socialnogo-partnerstvainformaciya-stranica-4.html
  • laboratornaya.bystrickaya.ru/programmnoe-obespechenie-sistemi-sbora-opisanie-i-instrukciya-po-ekspluatacii-g-obninsk.html
  • textbook.bystrickaya.ru/kak-sdelat-sherstyanie-tkani-i-sukno-nepromokaemi-obihodnaya-receptura-sadovoda-shtejnberg-pn.html
  • reading.bystrickaya.ru/leonardo-da-vinchi-1982-god-stranica-3.html
  • thesis.bystrickaya.ru/programma-disciplini-tehnologiya-stroitelnih-processov.html
  • college.bystrickaya.ru/1-tehnologicheskaya-podgotovka-proizvodstva-etap-tehnologicheskoj-podgotovki-proizvodstva-tesno-svyazan-s-predidushimi-etapami-tak-kak-vhodnoj-informaciej-dlya.html
  • teacher.bystrickaya.ru/fizicheskaya-kultura-i-adaptaciya-organizma-xxx-nauchno-metodicheskaya-konferenciya-vladivostok.html
  • gramota.bystrickaya.ru/zapolnenie-zayavki-na-uchastie-v-konkurse-prilozhenie-2-a-a-temkin-2-marta-2007-goda.html
  • literature.bystrickaya.ru/deyatelnost-municipalnogo-arhiva-otchet-glavi-municipalnogo-rajona-krasnochikojskij-rajon-za-2010god.html
  • school.bystrickaya.ru/kopchenie-i-koptilnie-kameri.html
  • uchit.bystrickaya.ru/titovichvladimir-vasilevich-ukazatel-personalij.html
  • crib.bystrickaya.ru/igrapriroda-igri-predmet-i-zadachi-psihologii-kak-nauki.html
  • books.bystrickaya.ru/dokumentaciya-ob-aukcione-na-pravo-zaklyucheniya-gosudarstvennogo-kontrakta-na-postavku-tovara-dlya-gosudarstvennih-nuzhd.html
  • esse.bystrickaya.ru/referat-otchet-97-str-47-illyustraciya-30-tablic-42-ispolzovannih-istochnika.html
  • writing.bystrickaya.ru/innovacionnaya-i-investicionnaya-deyatelnost-predpriyatiya.html
  • tasks.bystrickaya.ru/13092011-16092011-provedenie-vistavok-v-moskv-e-v-2011-godu.html
  • ucheba.bystrickaya.ru/prakticheskie-rekomendacii-teoreticheskie-i-metodologicheskie-osnovi-razvitiya-sestrinskogo-dela-na-urovne-pervichnoj.html
  • ekzamen.bystrickaya.ru/sabati-barisi.html
  • thesis.bystrickaya.ru/prilozhenie-17-metodicheskie-rekomendacii-dlya-organov-gosudarstvennoj-vlasti-subektov-rossijskoj-federacii-i-organov-mestnogo-samoupravleniya-po-realizacii-federalnogo-zakona-ot-8-maya-2010-g-83-fz-v-sfere-transporta.html
  • thescience.bystrickaya.ru/kasha-v-golove-fajnberg-v-l-inie-izmereniya-kniga-rasskazov.html
  • institut.bystrickaya.ru/stanca-i-prodolzhenie-tajnaya-doktrina.html
  • report.bystrickaya.ru/ii-mezhdunarodnaya-nauchno-prakticheskaya-konferenciya-voda-bescennoe-nasledie-sankt-peterburg-azimut-otel.html
  • literatura.bystrickaya.ru/rinochnaya-stoimost-nornikelya-sostavlyaet-po-raschetam-agentstva-bloomberg-29-mlrd.html
  • control.bystrickaya.ru/dialogovoe-proektirovanie-tehnologicheskih-processov-v-sisteme-tehnopro.html
  • zadachi.bystrickaya.ru/shpargalka-po-moskvovedeniyu.html
  • knigi.bystrickaya.ru/sovpadenie-imyon-sobitij-i-faktov-s-tem-chto-schitaetsya-realnim-sluchajnoe-stranica-6.html
  • © bystrickaya.ru
    Мобильный рефератник - для мобильных людей.