.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
  • turn.bystrickaya.ru/plan-raboti-centra-razvitiya-sistemi-dopolnitelnogo-obrazovaniya-detej-i-molodezhi-moskovskoj-oblasti-stranica-6.html
  • nauka.bystrickaya.ru/v-a-mihelson-v-a-grebennikov-stranica-8.html
  • tests.bystrickaya.ru/lekciya-3-2-chasa.html
  • learn.bystrickaya.ru/glava-18-socialnie-vzaimodejstviya-i-vliyaniya-uchebnik-dlya-studentov-universitetov.html
  • writing.bystrickaya.ru/audit-statutnogo-kaptalu-chast-8.html
  • doklad.bystrickaya.ru/uchebno-metodicheskij-kompleks-po-discipline-teoriya-gosudarstva-i-prava-rassmotreno-i-utverzhdeno-na-zasedanii-kafedri-protokolom-ot.html
  • testyi.bystrickaya.ru/apparat-polnomochnogo-predstavitelya-prezidenta-rossijskoj-federacii-v-uralskom-federalnom-okruge.html
  • thescience.bystrickaya.ru/informacionnij-byulleten-367-g-moskva-2010-god.html
  • education.bystrickaya.ru/102-sredstva-obsheniya-uchebnoe-posobie-dlya-studentov-pedagogicheskih-uchebnih-zavedenij.html
  • report.bystrickaya.ru/istoriya-zapadno-evropejskoj-muziki-do-1789-goda-tom-pervij-po-xviii-vek-stranica-12.html
  • kolledzh.bystrickaya.ru/astragalus-glycyphyllos-l-ekologicheskij-vestnik.html
  • gramota.bystrickaya.ru/vstrecha-pravoslavnoj-russkoj-ekklesiologii-s-katolicheskoj-ekklesiologiej-v-xix-xx-vv.html
  • shpargalka.bystrickaya.ru/v-altajskom-krae-planiruyut-sozdat-centr-po-problemam-antikrizisnogo-upravleniya-sliyaniya-i-poglosheniya.html
  • laboratornaya.bystrickaya.ru/rabochaya-programma-po-discipline-matematika-dlya-specialnosti-220301-avtomatizaciya-tehnologicheskih-processov-i-proizvodstv.html
  • doklad.bystrickaya.ru/uchebno-metodicheskij-kompleks-dlya-studentov-specialnostej-finansi-i-kredit-buhgalterskij-uchet-analiz-i-audit-stranica-2.html
  • tests.bystrickaya.ru/kontrolnaya-rabota-po-sociologii-14.html
  • student.bystrickaya.ru/18-zheltosandai-147-bjrii-zheke-zhne-zadi-tlalardi-tinishterin-arau-trtibi-turali.html
  • student.bystrickaya.ru/15-ocenka-velichini-yamr-signala-1-1-moment-kolichestva-dvizheniya.html
  • ekzamen.bystrickaya.ru/rossijskie-smi-o-mchs-monitoring-za-16-avgusta-2011-g.html
  • paragraph.bystrickaya.ru/linejnie-razmeri-uchebno-metodicheskij-kompleks-dlya-studentov-ekonomicheskih-specialnostej-080401-080502-vseh-form.html
  • portfolio.bystrickaya.ru/otrazhenie--predislovie-k-razdelu.html
  • education.bystrickaya.ru/2-tradicii-i-obichai-gendernij-vzglyad-dannoe-posobie-bilo-podgotovleno-v-ramkah-sovmestnogo-proekta-kirgizskoj.html
  • grade.bystrickaya.ru/o-polozhenii-o-byudzhetnom-processe-v-gorode-novosibirske.html
  • prepodavatel.bystrickaya.ru/strahovanie-chast-8.html
  • credit.bystrickaya.ru/organizaciya-osobo-ohranyaemih-prirodnih-territorij-l-o-karpachevskij-oficialnie-opponenti-doktor-biologicheskih-nauk.html
  • tetrad.bystrickaya.ru/uchebno-metodicheskij-kompleks-po-discipline-russkij-yazik-stranica-6.html
  • kanikulyi.bystrickaya.ru/yusyablokov-industrialnie-parki-instrument-uluchsheniya-investicionnogo-klimata-regionov-rossii.html
  • znaniya.bystrickaya.ru/publichnij-doklad-municipalnogo-obsheobrazovatelnogo-uchrezhdeniya-pirochinskaya-srednyaya-obsheobrazovatelnaya-shkola-kolomenskogo-municipalnogo-rajona-po-itogam-2006-2007-uchebnogo-goda.html
  • education.bystrickaya.ru/27vibrosi-v-rezultate-deyatelnosti-po-regeneracii-i-demontazhu-programma-organizacii-obedinennih-nacij-po-okruzhayushej.html
  • znaniya.bystrickaya.ru/programma-tura-5-dnej-4nochej-1-den-pyatnica-pribitie-v-london-aeroport-getvik-transfer-v-gostinicu-nedaleko-ot-aeroporta-hitrou.html
  • thescience.bystrickaya.ru/k-probleme-tipologii.html
  • uchitel.bystrickaya.ru/razdel-3-metodicheskie-ukazaniya-po-izucheniyu-konstitucionnogo-gosudarstvennogo-prava-rossijskoj-federacii.html
  • zadachi.bystrickaya.ru/rok-akademicki-stranica-15.html
  • ucheba.bystrickaya.ru/primtki-mezhotraslevoj-centr-kachestva-mck-prirost.html
  • klass.bystrickaya.ru/41-sushnost-i-principi-analiza-test-na-proverku-usvoeniya-materiala-temi-dlya-povtoreniya.html
  • © bystrickaya.ru
    Мобильный рефератник - для мобильных людей.