Графики и представянето им на компютър - учебна работа, реферат, курсова, дипломна работа!
Представя ви се документ: Графики и тяхното представяне на компютър.
Федерална агенция за образование
Федерална държавна образователна институция
висше професионално образование
Чувашки държавен университет И.Н. Улянова
Факултет по управление и икономика
Катедра Висша математика и информационни технологии
дисциплина: Дискова математика за програмисти
на тема:Графики и представянето им на компютър
→1. Дефиниция на графика
1.1 Основна дефиниция
1.3 Други определения
→2. Начини за задаване на графики
2.1 Графика на изображението
2.2 Начини за числено представяне на графики
2.3 Представяне на насочени графи
→3. Видове графики и операции върху тях
3.1 Графични елементи
3.2 Изоморфизъм на графиката
3.3 Тривиални и пълни графики
3.4 Двустранни графи
3.5 Насочени орграфи и мрежи
3.6 Операции върху графики
→4. Представяне на графики в компютър
4.1 Изисквания за представяне на графиките
4.2 Внедряване на алгоритми за търсене в дълбочина и в ширина в Turbo Pascal
Списък на използваната литература
Сред дисциплините и методите на дисковата математика теорията на графите и особено алгоритмите върху графи намират възможно най-широко приложение в програмирането. Между понятието графика и понятието връзка има дълбока връзка - по същество това са равнообемни понятия. Възниква естествен въпрос, защо тогава графиките са толкова очевидно предубедени? Факт е, че теорията на графите осигурява доста удобенезикза описаниесофтуерни (и много други) модели. Тази теза може да се обясни със следната аналогия. Понятието релация може да бъде напълно изразено и чрез понятието множество. Независимото определение на понятието отношениеобаче е по-удобно- въвеждането на специални термини и обозначения опростява представянето на теорията и я прави по-разбираема. Същото важи и за теорията на графите. Сложната система от специални термини и нотация на теорията на графите прави възможно просто и лесно да се опишат сложни и фини неща. Особено важно е да имате визуална графична интерпретация на концепцията за графика. Самоназванието "граф" предполага наличието на графична интерпретация. Картините ви позволяват незабавно да "видите" същността на въпроса на интуитивно ниво, допълвайки и украсявайки досадни рационални текстови доказателства и сложни формули.
Графиките представляват най-абстрактната структура, срещана в теорията на компютърните науки. Графиките се използват за описание на автоматични алгоритми за проектиране, в диаграми на краен автомат, при решаване на проблема с маршрутизирането на потока и др. Всяка система, която предполага наличието на дискови състояния или наличието на възли и преходи между тях, може да бъде описана с графика.
Например,ПроблемзаКьонигсбергмостове.Обиколете четирите части на земята, като преминете през всеки мост веднъж и се върнете към началната точка. Този проблем е решен от Ойлер през 1736 г.Проблемзамекскъщиимекскладенци.Има три къщи и три кладенеца. Да води от всяка къща до всеки кладенец на ҭҏᴏпинка, за да не се пресичат ҭҏᴏпинки. Този проблем е решен от Куратовски през 1930 г.Проблемзачетирицвята.Оцветете всяка карта в равнинатачетири цвята, така че да няма две съседни зони, боядисани с един и същи цвят.
ГрафG(V,E)е колекция от две множества - непразно множествоV(набор отвърхове)и множествоEот неподредени двойки от различни ϶lȇmens на множествоV(Eе набор отръбове).<1 2>
G ( V , E ) = V, E, V , E VV, E = E -
Връзките между възлите на графа се наричат ребра. Ако възлите на графиката не са номерирани, тогава ръбовете са неориентирани. Графика с номерирани възли има ориентирани ръбове. На ръбовете могат да бъдат присвоени специфични тегла или етикети. На фиг. 1.1A и 1.1B са примери за обикновен и насочен график.
Броят на върховете на графаAще бъде означен ср,, а броят на ребрата сq:
p := p ( A ) : = V , q : = = q ( A ) : = E ;
Една по-проста дефиниция на графика е колекция от точки и прави, в които всяка права свързва две точки. За насочена графа E ? Vx е краен набор от насочени ръбове. Ръбът може да бъде права линия или крива линия. Ребрата не могат да имат общи точки, освен върховете (възлите) на графиката. Една затворена крива в E може да има само една точка от множеството V, а всяка отворена крива в E има точно две точки от множеството V. Ако V и E са крайни множества, тогава графиката, съответстваща на тях, се наричакрайна. Графът се наричаизроденпри условие, че няма ребра.Паралелнитеръбове на графиката са тези, които имат общи начални и крайни възли.
Ако ребро свързва два върха, тогава казват, че им е инцидентно; върховете, свързани с ребро, се наричат съседни. Два върха, свързани с ребро, могат да съвпадат; такъв ръб се нарича контур. Броят на ръбовете, инцидентни на един връх, се нарича степенвърхове. Ако степента на един връх е 0, тогава се получава изолиран граф. Ако две ребра са инцидентни на една и съща група върхове, те се наричат множествени; граф, съдържащ множество ребра, се нарича мултиграф.
Забележка.Освен ако не е посочено друго, G+ се приема и е просто G.
АкоAVе набор от върхове, тогаваG(A)е набор от всички върхове, съседни на върхове отA:
Г (А) : = u V v A u Г ( v );
Често се разглеждат следните обекти, свързани с графики.
Ако елементите на множествотоEсаподреденидвойки, тогава графът се наричанасочен(илидиграф).В този случай елементите на множествотоVсе наричат възли, gami.
Ако елементът от множествотоEможе да бъде двойкаидентични(не различни) ϶елементиV,, тогава такъв елемент от множествотоEсе наричацикъл,и графиката се наричаграфсцикли(или <1 1> псевдограф).
АкоEне е набор, амножество, съдържащо няколко идентични елемента, тогава тези елементи се наричат множестворебра,и графиката се наричамултиграф.
Ако елементите на набораEне са непременно двуелементни, акоито и да еподмножества на набораV,тогава такива елементи на набораEсе наричат хипердъги,и графиката се наричахиперграф.
Ако функциятаE:VMи/илиF:EM,е дадена, тогава наборътMсе нарича набор отмарки,и графиката се наричамаркирана(илизаредена).<1 2> Обикновено като набор от етикетиизползват се букви или цели числа.
Графиките се показват на равнина като набор от точки и прави или вектори, които ги свързват. С това лицата могат да се показват и като криви линии, като дължината им не играе никаква роля.
Графика G се наричаплоска, ако може да бъде показана в равнина, без да пресича лицата си. Очертание на графика (лице) е всяка топологично свързана област, ограничена от ръбове на графика.
Казва се, че неориентиран граф G = есвързан, ако за всеки два възела x,y ⊂ V има последователност от ребра от множеството E, свързваща x и y. Граф G е свързан тогава и само ако множеството от неговите върхове не може да бъде разделено на 2 непразни подмножества V1 и V2, така че и двете гранични точки на всяко ребро да са в едно и също подмножество. Казва се, че граф G еk-свързан(k і 1), ако няма набор от k-1 или по-малко възли V`H V, така че изтриването на всички възли V` и техните спрегнати ребра ще направи G несвързан.
ТеоремаMenger: граф G е k-свързан тогава и само ако всеки 2 различни възела x и y на графика G са свързани с поне k пътеки, които не съдържат общи възли. k-свързаните графики са от особен интерес за мрежови приложения. Известен проблем е автоматичното показване на графиката на екрана или хартията. В допълнение, за много приложения (например CAD), всички възли на графиката трябва да съвпадат с възлите на технологичната мрежа. Има и други ограничения, като например необходимостта всички възли да се поставят на права линия. В този случай ръбовете на графиката могат да бъдат криви линии, дъги или начупени линии, състоящи се от линейни сегменти.
2.2 Начини за числено представяне на графика
→1. Матричен метод (с помощта наматрици на съседство). Матрицата на съседство има m - сҭҏᴏк и n - колони, където m е броят на върховете на графиката.
Елементите на матрицата на съседство са 0 и 1. Ако върховете са свързани, тогава се задава 1 и обратно.