Phenquestions
Възел в графика се нарича връх (множествено число - върхове). Понякога все още се нарича възел; може да се нарече и точка. Връзка в графика се нарича ръб. Понякога все още се нарича връзка; може да се нарече и линия.
Графика с много функции
Тази фигура показва графика с много функции:
Кръговете (дисковете) са върхове. Всяка права линия или извита линия или линия е ръб.
Характеристики на графиката
Връх
Върхът е обект. Може да е къща; може да е човек; може да е абстрактно съществително; това може да е всеки обект, за който се сетите.
Ръб, край
Ръбът е връзка (връзка) между два върха; връзката може да е абстрактна.
Примка
Цикълът е ръб, който свързва върха със себе си.
Arrow Edge
Да разгледаме двама души: Йоан и Петър. Ако Джон заеме на Питър 100 долара и ако Джон и Петър са върхове, тогава ръбът на заемата ще сочи към Петър. Ако и двамата партньори забравят, че Петър дължи на Джон, а Петър заема на Джон $ 100, тогава в другия край на същия ръб, стрелка ще сочи към Джон. Ако Петър даде на Джон само 75 долара, а не 100 долара, тогава различен ръб ще свърже Петър с Джон. Този втори ръб ще има върха на стрелката, сочещ към Джон. Във втория случай има два ръба, всеки с по една стрелка, насочени в противоположни посоки.
Върхът, към който сочи ръбът, е върх на главата за този ръб. Върхът, от който тръгва ръбът, е връх на опашката.
Инцидент
Ръбът свързва два върха. Казва се, че ръбът пада върху двата върха. Не е необходимо ръбът да има стрелка. Двата върха са известни като крайни точки на ръба. Възможно е да има графика, където връхът не принадлежи на никой ръб, но това няма да бъде разгледано в този урок.
Ненасочена графика
Ръбът може да бъде стрелка или не. Графика, при която никой ръб не е стрелка, е неориентирана графика. Ръбът може да бъде представен от права линия или крива или линия.
Насочена графика
Графика, където всеки ръб е стрелка (посока), е насочена графика. Ръбът на стрелката може да бъде представен от права линия със стрелка или крива със стрелка или контур със стрелка.
Липсата на посока на ръба на неориентирана графика означава, че всеки ръб на ненасочената графика е двупосочен.
Степен на върха
Броят на ребрата, които попадат върху върха, е степента на върха. Цикълът има два случая на връх, така че цикълът се брои два пъти.
Ред на графика
Редът на графиката е броят на върховете в графиката.
Мултиграф
Мултиграф е графика, където за някои двойки върхове има повече от един ръб. Ненасочената мултиграфия е такава графика, в която ръбовете нямат посоки (не са стрелки). Насочен мултиграф е този, при който всеки ръб е стрелка, а за двойки върхове, които имат повече от една стрелка, единият връх е опашката на тези стрелки, а другият връх е главата на същите стрелки. Следващата диаграма показва неориентиран мултиграф:
Повече от един ръб (т.е.д. множество ребра) за двойка върхове също се наричат успоредни ребра.
Колчан
Колчанът е мултиграф, който позволява цикли (един или повече цикли). Някои мултиграфии не позволяват цикли.
Проста графика
Простата графика е графика, при която няма две двойки върхове, които имат множество ръбове. Цикли не са разрешени в обикновена графика.
Празна графика
Празната графика е графика без върхове и следователно без ръбове.
Смесена графика
Смесената графика е графика, където някои ръбове са стрелки, а други не; с други думи: някои ръбове имат посоки, а други не са насочени.
Претеглена графика
Възможно е да има графика, в която число, известно като тегло, е присвоено на всеки ръб. Някои ръбове имат един и същ номер, но числата обикновено са различни. Такава графика се нарича претеглена графика. Числата за конкретна графика могат да представляват дължини или разходи (цени) или някакъв размер, в зависимост от проблема.
Несъгласие и превишение
Речникът, степента и степента са приложими само за насочена графика. Графиката може и да не е мултиграф. Графиката може да има или не цикли.
Броят на върховете на стрелките, свързани към върха, е степента на този връх. Стрела с единичен връх на стрелата има края на главата и края на опашката. Броят на опашките, свързани с върха, е извън степента на този връх.
Забележка: Графика с множество ръбове за двойката върхове, където множеството ръбове са в противоположни посоки, не е адресирана в този урок.
Софтуерно представяне на графика
Графиката може да бъде представена в софтуера по начина, по който е нарисувана на диаграмата. Графика може да бъде представена и в софтуер чрез математическа матрица (двумерен масив). Една от тези матрици се нарича матрица на съседство.
Матрица на съседство
Матрицата на съседство е квадратна матрица. Заглавията на редовете са всички върхове, написани във възходящ ред. Заглавията на колоните са все същите върхове, написани във възходящ ред. Преброяването на редовете или колоните на матрица започва от 1, а не от нула, както при масивите. Когато се идентифицира елемент в матрица, номерът на реда се записва първо преди номера на колоната.
За неориентирана графика всеки запис (елемент) в матрицата на съседство е броят на ръбовете, свързващи двата съответни върха. Един цикъл трябва да се брои два пъти. За насочена графика всеки запис в матрицата на съседство е или броят на ръбовете, оставящи върха на реда и влизащи в съответния връх на колоната, или е броят на ръбовете, напускащи върха на колоната и влизащи в съответния връх на реда. Изборът е този на програмиста. В тази ситуация (и в двата случая) цикъл все пак трябва да се брои веднъж.
Забележка: Графиката е диаграма е сама по себе си структура от данни. Матрицата на съседство също е структура на данни сама по себе си.
Ненасочена графика и матрица на съседство
Следващите диаграми показват ненасочена графика и съответната матрица на съседство:
Водещият диагонал на матрицата е диагоналът отгоре вляво вдясно отдолу. Ненасочената матрица е симетрична спрямо водещия диагонал. Вписването в матрицата за ред A и колона C е 1, което означава, че има един ръб, свързващ връх A и връх C. Вписването в матрицата за ред C и колона B е 3, което означава, че има 3 ръба, свързващи връх C и връх B. По същия начин са обяснени и останалите записи.
Сумата от записите за ред дава броя на ръбовете (градуса) за съответния връх. Сумата от записите за ред A е 2, което означава, че 2 ръба са свързани с връх A. Сумата от записите за ред B е 6, което означава, че 6 ръба са свързани с връх B. Останалите записи са обяснени по подобен начин.
Насочена графика и матрица на съседство
Следващите диаграми показват насочена графика и съответната матрица на съседство:
Матрицата на съседство за насочена графика не е непременно симетрична спрямо водещия диагонал. Записът на матрицата за ред A и колона C е 1, което означава, че един ръб напуска от връх A към връх C. Записът на матрицата за ред C и колона B е 3, което означава, че 3 ръба остават от връх C до връх B. По същия начин са обяснени и останалите записи.
Сумата от записите за колона дава степента за върха (колона). Сумата от записите за ред дава степента за върха (ред). Сумата от записите за колона A е 1, което означава, че един ръб е насочен към връх A. Сумата от записите за ред B е 2, което означава, че 2 ръба остават от връх B. Останалите записи са обяснени по подобен начин.
Графични операции
Структурата на данни, като графика, се състои от набор от стойности на данни или набор от обекти, плюс връзката между обектите, плюс операциите (функциите) между обектите. Връзките в графика са обозначени с ръбовете. Освен това графиката трябва да има поне следните операции:
съседен (G, x, y)
G означава графика. Тази операция проверява дали ръбът свързва връх x и връх y. Стойността и позицията на запис в матрица показват връзката на ръб (и неговия тип).
съседи (G, x)
Тази операция връща списък с всички върхове, които са директно свързани с върха x. Стойността и позицията на запис в матрица показват връзката на ръба.
remove_vertex (G, x)
Тази операция премахва връх x от графика. Ако върхът нямаше ръб, няма проблем. Ако обаче връхът има връзки, тогава връзките (ръбовете) също трябва да бъдат премахнати. Стойността и позицията на запис в матрица показват наличието на определен връх. Ако даден връх бъде премахнат, матрицата трябва да бъде пренастроена.
add_vertex (G, x)
Това добавя връх x без добавяне на ръбове или замества връх, който е имал ръбове, но е бил премахнат. Стойността и позицията на запис в матрица показват наличието на определен връх. Ако се добави връх, матрицата трябва да бъде пренастроена.
add_edge (G, x, y)
Тази операция добавя нов ръб между върха x и върха y, ако ръбът не е бил там. Стойността и позицията на запис в матрица показват наличието на определен ръб. Ако се добави ръб, матрицата трябва да бъде пренастроена.
remove_edge (G, x, y)
Тази операция би премахнала ръба между върха x и върха y, ако ръбът беше там. Стойността и позицията на запис в матрица показват наличието на определен ръб. Ако ръбът е премахнат, матрицата трябва да бъде пренастроена.
get_vertex_value (G, x)
Тази операция връща стойността, v, свързана с върха, x. За да постигнете това, ви е необходим набор от мощности от подмножества за етикети на върхове и техните стойности.
set_vertex_value (G, x, v)
Тази операция дава нова стойност, v за стойността, свързана с върха, x. За да постигнете това, ви е необходим набор от мощности от подмножества за етикети на върхове и техните стойности.
Някои графики асоциират стойности и с техните ръбове. Такива графики се нуждаят от следните допълнителни операции:
get_edge_value (G, x, y)
Тази операция връща стойността, v, свързана с ръба, (x, y). За да постигнете това, ви е необходим набор от мощности от подмножества за ръбове и техните стойности.
set_edge_value (G, x, y, v)
Тази операция дава нова стойност, v за стойността, свързана с ръба, (x, y). За да постигнете това, ви е необходим набор от мощности от подмножества за ръбове и техните стойности.
Заключение
Графиката е набор от върхове, свързани с ръбове. Графиката може да бъде насочена или насочена. Ръбовете могат да бъдат ненасочени или насочени. Циклите могат да присъстват или да липсват в графика. Това, което трябва да научите по-нататък, е настройка, настройка на мощността и мулти-набор, свързани с графики. След това трябва да научите различните видове графики, като ориентирана графика, обикновена графика, пълна графика, двустранна графика, турнирна графика, графика на поточната мрежа и т.н.
Chrys
За автора
Хризант Форча
Откривател на интеграцията на математиката от Първи принципи и свързаните с нея поредици. Магистърска степен по техническо образование, специализирана в електроника и компютърен софтуер. BSc Electronics. Също така имам знания и опит на ниво магистър по компютърни технологии и телекомуникации. От 20 000 писатели бях 37-ият най-добър писател в devarticles.com. Работя в тези области повече от 10 години.
Вижте всички публикации
