Теория на графиките: основни определения

Теорията на графиките е клон на математиката, използван в компютърните науки и програмиране, икономиката, логистиката и химията.

Какво е графика

Често графичните системи се използват за описване на структурата на системите. Елементите в тях са представени от кръгове, точки, квадрати и т.н., а връзките между елементите са линии или стрелки. В същото време не е важно как са изобразени елементите, нито каква е дължината или формата на линиите - само какви елементи са свързани. По този начин, графика е чифт от формата (A, M), където A е краен набор от върхове, а M е набор от ръбове - линии, свързващи някои върхове.

Основни понятия на теорията на графите

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

За неориентиран график (виж фигурата по-долу), ръбовете са представени от линии без ориентация. Съответно, двойката върхове, с които ръбът се свързва, е неуправляван. И двата върха са краищата на ръба.

Ако върховете a и b са краищата на един ръб (или началото и края на дъга) на една графика, тогава ние казваме, че върховете a и b са инцидентни на този ръб (дъга), а ръбът (arc) е инцидент към върховете a и b. Ако върховете a и b са краищата на ръба, то те (a и b) се наричат ​​съседни.

Най-често разглеждаме графиките, чиито ръбове са от един и същи тип - ориентирани или не.

Ако краищата имат едно и също начало и край, те се наричат ​​многократни ръбове, а графиката, в която те присъстват, се нарича мултиграф.

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

Най-често срещаните не-ориентирани графики, които нямат многобройни ръбове и без цикли. Такива графики се наричат ​​обикновени. Те нямат множество ръбове, така че можете да идентифицирате ръба и съответната двойка върхове.

Всеки връх на диграфа се характеризира с:

• Половин резултат. Това е броят на дъгите, излизащи от него.
• Indegree. Това е броят на дъгите, които влизат в даден връх.

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

Във неориентиран график всеки връх се характеризира със степента на върха. Това е броят на ръбовете, които са инцидентни на върха. Общата сума на степените на върховете на графиката е броят на ръбовете, умножен по две: всеки ръб ще даде принос, който е равен на два.

Връх със степен 0 се нарича изолиран.

Висящият връх е връх с степен 1.

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

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

Графове: изоморфизъм

Концепцията за изоморфизма се използва в математиката. По-специално, теорията на графите го дефинира по следния начин: две графики U и V са изоморфни, ако има биекция между множествата на техните върхове в тези графики: всеки 2 върха в графиката U е свързан с ръб, ако и само ако един и същ в графиката V върхове (които могат да се наричат ​​по различен начин). Фигурата по-долу показва две изоморфни графики, в които между върховете, изобразени в еднакви цветове в първия и втория графики, е описаната по-горе биекция.

Пътища и цикли

Път в неориентиран или ориентиран граф е поредица от ръбове, като всяка следваща започва от върха, в която завършва предишният. Един прост път е този, в който всички върхове, с изключение, може би, първоначалното и крайното, и ръбовете са различни. Цикълът в диграфа е път, чийто начален и краен върхове съвпадат и който включва поне един ръб. Цикъл в неориентиран граф е път, който съдържа най-малко три различни ръба. Във втората фигура цикълът е например пътят (3, 1), (6, 3), (1, 6).

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