Определяне на графиката, H4S

Предишен ◈ Следващото

Ненасочена графика с шест върхове и седем ръбове

В математическа теория графика и компютърна графика - набор от не-празен набор от върховете и набор от двойки на върховете.







Обектите са представени като върхове. или графиката възли и връзки - като дъга. или ребра. За различни приложения, могат да бъдат ориентирани към различни видове графики, ограничения по отношение на броя на връзките и допълнителни данни за върхове или ръбове.

Много структури на практически интерес към математиката и компютърните науки, могат да бъдат представени чрез графики. Например, структура Уикипедия може да се моделира с насочен граф (диграфът), в която на върха - тази статия, и дъги (ориентирани подкастрени) - (. Виж тематична карта) хипервръзки.

дефинира

  • V е не-празен набор от върха или възли,
  • Е е набор от двойки (в случай на ненасочена графика - неподреден) върхове, наречени ръбове.

V (и следователно Е. иначе би било MultiSet), обикновено се считат за ограничени комплекти. Много добри резултати за крайните графиките, неправилно (или по някакъв начин е различно) за безкрайно графики. Това е така, защото редица съображения, че е невярна в случая на безкрайните множества.

Върхове и ръбове на графиката се наричат ​​също елементи на графиката, броят на върховете в графика | V | - ред. броят на ръбове | E | - размера на графиката.

Върхове U и V са наречени крайни възли (или завършва) ръбове е = U, V>. Edge, от своя страна, се свързва върха. Две крайни върхове на една и съща ребро се наричат ​​съседите.

Две краища се наричат ​​съседни. ако те имат една обща цел връх.

Две краища се наричат ​​кратни. ако множество крайни върхове съвпадат.

Един ръб се нарича линия. Ако краищата са еднакви, т.е. е = о, о>.

Степен ° С V V пикове по броя на ръбовете, за които е край (линия се счита два пъти).

Vertex се нарича изолирани. ако това не е краят на всяка перка; висящи (или лист), ако тя е в края на точно един ръб.

насочена графика

Arc - една наредена двойка върхове (V, W). където връх V се нарича самото начало, и w - дъга край. Можем да кажем, че дъгата води от връх обем до Vertex вата

смесена граф

Смесени grafG - графика, в които могат да бъдат ориентирани някои ръбове, а някои - ненасочена. Записите са подредени тройна G. = (V, Е, А), където V. Е и А са определени по същия начин както по-горе.

Ориентирани и не са ориентирани графики са специални случаи на смесени.

изоморфни графики

Графика G се нарича изоморфни графика Н. Ако има Биекция е от множеството върхове в графика G H. множество върхове имащи следната имота: ако графиката G има ръб от връх до връх А в графика Б. Н трябва да бъде предимство от F на връх ( а) в горния F (в) и обратно - ако пространство H е ръб от връх до връх на в В. grafeG бъде предимство от връх е - 1 (а) до е на връх - 1 (в). В този случай, насочено графиката трябва да поддържа ребро Биекция ориентация. В случай на претеглена графика Биекция също трябва да запазят ребра тегл.

Други свързани с определение

Път (или верига) на графиката е ограничен последователност на върховете, където всеки връх (с изключение на последния) е свързан към следващата в последователността на върховете на ръба.

Ориентирани от диграфа е ограничен последователност на върховете VI, което за всички двойки (VI, VI + 1) са (ориентирани) ръбове.







Един цикъл е път, по който първия и последния върховете са едни и същи. Когато etomdlinoy път (или цикъл) е броят на съставните ръбове. Забележете, че ако върховете U и V са краищата на ръба, а след това, съгласно определението, последователност (U, V, U) е цикъл. За да се избегнат подобни "изродени" случаи, да се въведе следните понятия.

На път (или цикъл) се нарича просто. ако краищата не се повтарят; елементарен. ако тя е проста и върхове в нея не се повтарят. Лесно е да се види, че:

  • Всеки начин за свързване на двете върховете съдържа елементарен път, свързващ същите два върхове.
  • Всеки прост път съдържа не-елементарни елементарен цикъл.
  • Всеки прост цикъл, преминава през връх (или ребро) soderzhitelementarny (под) контур, простиращ се през същия връх (или ръб).
  • Loop - елементарен цикъл.

А двоичен отношение на снимачната площадка на върха, определени като "има път от ф да о», е връзка равностойност. и, следователно, се разпада на снимачната площадка на равностойност класове, наречени елементи на графиката. Ако графът е точно един свързан компонент, графиката е свързан. В свързан компонент може да се въведе ponyatierasstoyaniya между върховете като минималната дължина на пътя свързването на тези върхове.

Всяка максимална свързан подграф на графика G е свързан компонент (или компонент) на графиката G. Думата "максимум" означава включването на максимум, който не се съдържа в свързано подграф с голям брой елементи

Edge на графиката се нарича мост. ако му заличаване увеличава броя на компонентите.

Допълнителни характеристики на графика

  • свързани. Ако по някаква два върха U, V е път от ф да ст.
  • ориентирани силно свързан или свързан. ако е ориентирана и от всеки възел на всяко друго има насочена път.
  • дърво. Ако е свързан и не съдържа прости цикли.
  • пълна. ако всеки от два (за висока, ако не е позволено линия), неговите върховете свързан с ръба.
  • двустранен. ако върховете могат да бъдат разделени в две подгрупи несвързани V1 и V2, така че всеки ръб свързва връх на V1 връх от V2.
  • K-Долни. ако върховете могат да бъдат разделени в к несвързани подгрупи V1, V2. ..., Vk, така че няма да има ръбове, свързващи върховете на една и съща подгрупа.
  • пълен двустранен. ако всеки връх на една подгрупа е свързана с ръба на взаимно връх подгрупа.
  • равнинни. ако графиката може да бъде представен от диаграмата на самолета без преминаване ръбове.
  • претеглена. Ако всеки край се задава определен брой наречен теглото на ръба.

Начини да представляват графика по компютърни науки

матрица близост

Таблица където колоните и редовете съответстват на върховете на графиката. Във всяка клетка на броя на матрицата се записва, като се посочва дали комуникация от най-горния ред към върха на колона (или обратно) на.

Недостатъкът е, изискванията за памет е право пропорционална на квадрата на броя на върховете.

  • Двуизмерният масив;
  • Matrix с пропуски;
  • Косвената позоваването (с помощта на функцията).

честота матрица

Всеки ред съответства на специфична връх на графиката, а колоните съответстват на графика отношения. Клетката в I-та линия с J-тата колона на матрицата е писано:

1, ако връзката й «навън» на върха и. -1 ако връзката "част" в горната част, 0 във всички други случаи (тоест, ако връзката е контур или съобщение не е инцидент в началото)

Този метод е най-обемен (размерът е пропорционална | E | | V |) за съхранение, но е по-лесно да се намери цикли в графиката.

списък на ребрата

Списък на ръбове - е вид графика представяне в паметта на компютърна програма, се счита, че всеки край е представена от две числа - числата на върховете на ребрата. Списък на ребрата е по-удобно да се прилагат различни алгоритми за графики, в сравнение с матрицата на съседство.

Обобщаването на понятието графика

Повече абстрактно, графиката може да се дефинира като три (V, E, φ), където V и Е - Някои комплекти (върхове и ръбове съответно ..), и - функция на честотата (или incidentor), която определя на всеки ръб (подредени или неподреден) двойка vershinu и обем V (всичко). Специфични случаи на тази концепция са:

  • насочени графики (digraphs) - когато φ (д) винаги е подредена двойка върхове;
  • неориентирани графа - където φ (д) винаги е нарушено двойка върхове;
  • смесени графики - в които има двете насочени и неориентирани ръбове и линии;
  • Ойлер графики - графика, в която има кръгова траектория Ойлер (Ойлер цикъл).
  • мултиграф - графики с множество ръбове, които имат техните краища същата двойка върхове;
  • pseudographs - това мултиграф признава съществуването на електрически вериги;
  • прости графики - без линии и множество ръбове.

Определението не пасва на някои от другите обобщенията, дадени по-горе:

литература







Предишен ◈ Следващото