§ 6.1: Определение графа. Ориентированные и неориентированные графы - Приднестровский государственный университет...
.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
  • college.bystrickaya.ru/1obosnovanie-neobhodimosti-razrabotki-programmi-oblastnaya-celevaya-programma-okazanie-sodejstviya-dobrovolnomu.html
  • composition.bystrickaya.ru/ov-kuvarzina-nizhnij-novgorod-sbornik-statej-po-materialam-vserossijskoj-nauchnoj-konferencii-23-24-aprelya.html
  • klass.bystrickaya.ru/5-osnovnie-trebovaniya-k-priboram-ucheta-teplovoj-energii-pravila-ucheta-teplovoj-energii-i-teplonositelya-utv.html
  • university.bystrickaya.ru/glava-chetirnadcataya-u-burdesov-ne-skuchno-kniga-tretya.html
  • school.bystrickaya.ru/gfk-group-specializirovannie-smi-analiz-upominaemosti-v-smi-romir-i-konkurentov-obzor-smi-za-18-maya-2009-god.html
  • lektsiya.bystrickaya.ru/programma-duhovno-nravstvennogo-vospitaniya-detej-starshego-doshkolnogo-vozrasta.html
  • knigi.bystrickaya.ru/shtik-roman-kulikov-ezhi-tumanovskij-stranica-10.html
  • letter.bystrickaya.ru/obshinski-svet-grad-dobrich.html
  • desk.bystrickaya.ru/plan-meropriyatij-gosudarstvennoj-universalnoj-nauchnoj-biblioteki-krasnoyarskogo-kraya-na-dekabr-2008-goda-.html
  • knigi.bystrickaya.ru/sovremennie-tendencii-obyazatelnogo-strahovaniya-grazhdanskoj-otvetstvennosti-vladelcev-transportnih-sredstv-opit-es-i-rossii-08-00-14-mirovaya-ekonomika-08-00-10-finansi-denezhnoe-obrashenie-i-kredit.html
  • university.bystrickaya.ru/glava-9-prikaz-gosudarstvennogo-komiteta-po-nauke-i-tehnologiyam-respubliki-belarus.html
  • kanikulyi.bystrickaya.ru/zharatilistanu-pndern-pnarali-bajlanista-oitu-arili-ekologiyali-blm-men-trbie-beru.html
  • obrazovanie.bystrickaya.ru/prishlo-novoe-vremya-posvyashaetsya-pamyati-l-pismo-rasshifrovka-moskovskogo-nebesnogo-poslaniya-k-chelovechestvu.html
  • doklad.bystrickaya.ru/unichtozhit-rossiyu-vesnoj-1941-g-dokumenti-specsluzhb-sssr-i-g-1937-1-94s-gg-vladimir-yampolskij-unichtozhit-rossiyu-vesnoj-1941-g-stranica-4.html
  • uchitel.bystrickaya.ru/rabochaya-programma-disciplini-matematicheskie-osnovi-obshej-teorii-sistem-napravlenie-oop-010400-prikladnaya-matematika-i-informatika.html
  • reading.bystrickaya.ru/kontrolnaya-po-statistike-chast-5.html
  • student.bystrickaya.ru/-2-obem-harakter-i-razmer-vozmesheniya-vreda-prichinennogo-zhizni-ili-zdorovyu-voennosluzhashih.html
  • ekzamen.bystrickaya.ru/rossijskie-smi-o-mchs-monitoring-za-27-iyulya-2011-g.html
  • upbringing.bystrickaya.ru/kto-mi-stranica-3.html
  • esse.bystrickaya.ru/rabochaya-programma-po-uchebnomu-predmetu-geometriya-10-a-klass.html
  • lektsiya.bystrickaya.ru/programma-disciplini-diskretnaya-matematika-i-matematicheskaya-logika-semestr.html
  • paragraf.bystrickaya.ru/zatrati-truda-na-osvoenie-uchebnoe-posobie-aspirantam-moskva-2003-a-g-vojtov-filosofiya-uchebnoe-posobie.html
  • abstract.bystrickaya.ru/2-iyunya-2009-g-n-36-ob-utverzhdenii-i-vvedenii-v-dejstvie-obshegosudarstvennogo-klassifikatora-respubliki-belarus-okrb-011-2009-specialnosti-i-kvalifikacii-stranica-24.html
  • desk.bystrickaya.ru/podgotovka-i-provedenie-chetiryoh-prosvetitelskih-seminarov-na-primere-osnovnih-aspektov-obshestvennogo-uchastiya-v-sfere-obrazovaniya.html
  • literature.bystrickaya.ru/doklad-gbou-brgi-3-tema-nad-kotoroj-rabotaet-uchrezhdenie.html
  • shkola.bystrickaya.ru/predmet-zadachi-i-terminologicheskij-apparat-kursa-stranica-25.html
  • institut.bystrickaya.ru/tarifami-zdes-vi-najdete-otveti-na-voprosi-kotorie-kasayutsya-kazhdogo-iz-nas-iz-chego.html
  • student.bystrickaya.ru/3-metodiki-lecheniya-oglavlenie-poyasnitelnaya-zapiska.html
  • nauka.bystrickaya.ru/uchebno-metodicheskij-kompleks-po-kursu-sovremennie-otechestvennie-sistemi-avtomatizacii-deloproizvodstva-i-elektronnogo-dokumentooborota-saded-barnaul-2007-stranica-5.html
  • write.bystrickaya.ru/glava-19-o-tom-kak-bog-yavilsya-na-svadbu-leo-taksil.html
  • desk.bystrickaya.ru/otchet-o-rezultatah-samoobsledovaniya-altajskogo-filiala-fgou-vpo-sibirskaya-akademiya-gosudarstvennoj-sluzhbi.html
  • occupation.bystrickaya.ru/neobhodimost-v-effektivnih-i-uproshennih-processah-peresecheniya-granici-v-pogranichnih-kontrolnih-punktah.html
  • learn.bystrickaya.ru/glava-10-kak-obespechivalas-bezopasnost-stalina-obshee-opisanie-dokumentov-i-srazu-zhe-voprosi-strannij-podbor-vrachej.html
  • lesson.bystrickaya.ru/prilozhenie-1-spravochnoe-gosudarstvennaya-sistema-sanitarno-epidemiologicheskogo-normirovaniya-rossijskoj-federacii.html
  • college.bystrickaya.ru/21-karta-rejting-kontrolya-organizacionno-normativnaya-dokumentaci-uchebnaya-programma-kursa-teoriya-i-metodika.html
  • © bystrickaya.ru
    Мобильный рефератник - для мобильных людей.