20508

Неорієнтовані та орієнтовані графи

Доклад

Информатика, кибернетика и программирование

Граф це сукупність об'єктів із зв'язками між ними. Об'єкти розглядаються як вершини або вузли графу а зв'язки як дуги або ребра. Для різних областей використання види графів можуть відрізнятися орієнтовністю обмеженнями на кількість зв'язків і додатковими даними про вершини або ребра.

Украинкский

2013-07-25

27 KB

28 чел.

Неорієнтовані та орієнтовані графи.

Граф — це сукупність об'єктів із зв'язками між ними.

Об'єкти розглядаються як вершини, або вузли графу, а зв'язки — як дуги, або ребра. Для різних областей використання види графів можуть відрізнятися орієнтовністю, обмеженнями на кількість зв'язків і додатковими даними про вершини або ребра.

Велика кількість структур, які мають практичну цінність в математиці та інформатиці, можуть бути представлені графами.

Неорієнтований граф

Граф або неорієнтований граф  — це впорядкована пара , для якої виконуються наступні умови:

— множина вершин або вузлів,

— множина пар (у випадку неорієнтованого графу — невпорядкованих) вершин, які називають ребрами.

(і так само ) зазвичай вважаються скінченними множинами. Велика кількість результатів, отриманих для скінченних графів, невірна (або інша) для нескінченних графів. Це пов'язано з тим, що певний набір ідей стає хибним у випадку нескінченних множин.

Орієнтований граф

Граф, який містить тільки ребра називається неорієнтованим, який містить тільки дуги — орієнтованим. Граф, що має як ребра так і дуги, називається мішаним. Якщо пара вершин сполучається кількома ребрами чи дугами одного напрямку, то ребра (дуги) називають кратними (паралельними). Дуга чи ребро що сполучає вершину саму із собою називається петлею. Граф без кратних дуг і петель називається простим.

Вершини сполучені ребром чи дугою називають суміжними, також називають суміжними ребра, що мають спільну вершину. Ребро (чи дуга) і її вершина називаються інцидентними. Ребро (u, v) з'єднує вершини u і v, дуга (u, v) починається у вершині u і закінчується у вершині v.

Кожен граф можна відобразити в евклідовому просторі множиною точок, які відповідають вершинам, сполучених лініями, що відповідають ребрам (дугам).


 

А также другие работы, которые могут Вас заинтересовать

21087. Экологизация научно-технического прогресса 82 KB
  Общественные и государственные интересы Интересы потребителей Интересы производителей Рынок экологических инноваций Вторичный рынок экологических товаров Первичный рынок экологических разработок Спрос Предложение Спрос Предложение Мотивационный механизм потребления экологических товаров 1 Мотивационный механизм производства экологических товаров 2 Мотивационный механизм внедрения инновационных разработок 3 Мотивационный механизм разработки инновационных проектов 4 Тема 8: Экологизация научнотехнического прогресса...
21088. Розвиток освіти у XIX - на початку XX ст 22.7 KB
  Було затверджено чотири типи шкіл: парафіяльні повітові губернські гімназії університети. Проміжне становище між гімназіями та університетами займали ліцеї яких на Україні було три: Рішельєвський в Одесі з 1817 p. стало заснування на східноукраїнських землях університетів які завдяки загальноєвропейській реформі університетської освіти швидко почали відігравати велику роль у культурному житті в розвитку науки. Перший університет на українських землях у складі Російської імперії засновано 1805 р.
21089. Розвиток науки у XIX - на початку XX ст 20.63 KB
  Всебічно обдарованим і феноменально працездатним був перший ректор Київського університету М. У розвиток філософської та філологічної наук суттєвий внесок зробив перший ректор Харківського університету І. Засновником вітчизняного слов’янознавства був професор Харківського університету І. ректором Харківського університету був Т.
21090. Розвиток літератури у XIX - на початку XX ст 27.79 KB
  Цей бурлескнотравестійний твір є однією з найбільш талановитих переробок поеми римського поета Вергілія в якій автор подав панорамну картину українського народного життя. Обидва письменники були визначними організаторами театрального життя першої половини XIX ст. Поетизація Гоголем українського життя і національного характеру романтичне зображення минулого українського народу сприяли широкому зацікавленню історією та етнографією України збуджували патріотичні почуття і стверджували гуманістичні цінності в українській культурі. Величні...
21091. Архітектура XIX - початку XX ст 15.03 KB
  У класицистичній манері будуються численні споруди в західноукраїнських містах. Романтичний настрій створювався не так самою архітектурою скільки природним оточенням споруд. На формі споруд позначилося впровадження нових будівельних матеріалів і технологій. До української культури на віки увійшли такі архітектурні споруди як Одеський та Львівський оперні театри Г.
21092. Образотворче мистецтво XIX–початку XX ст 24.18 KB
  Художники ніби намагаються стерти межі між класицизмом і романтизмом досягаючи при цьому значних успіхів у торуванні шляхів до цілком реалістичного живопису. Розширення меж тематичного арсеналу портретного живопису вже у другій половині XIX ст. Розвиткові живопису в Україні XIX ст. Соколов справжнім шедевром пізньоромантичного живопису є його картина Дівчата ворожать уночі проти Івана Купала з двома центрами освітлення маленьким каганцем і яскравим повним місяцем які надзвичайно виразно окреслюють постаті групи дівчат у човні.
21093. Музика і театральне мистецтво XIX - початку XX ст 18.06 KB
  Опинившись у залежності від російського субкультурного середовища народна українська музична культура дещо законсервувалася у своєму розвитку більше того у вжитку з’являються непритаманні українській музичній культурі містечкові романси казармені пісні тощо. у професійній музиці з’являються перші симфонічні твори Українська симфонія і симфонія сольмінор з Козачком невідомих авторів. Невід’ємною складовою національного театру була українська музика. Українська професійна музична школа спиралася на здобутки як української так і...
21094. Розвиток культури у добу Національно-демократичної революції (1917 - 1920 рр.) 18.88 KB
  Політика Тимчасового уряду в галузі народної освіти була демократичнішою ніж царського уряду і тому вже в березні 1917 р. Справжнім виразником інтересів українського громадянства і учительства у справі освіти стала Центральна Рада – представницький політичний орган українського народу утворений 7 березня 1917 р. Велику підтримку і допомогу надавали їй українські громадянські організації: товариство шкільної освіти учительські організації товариство Просвіта. було створено Генеральний секретаріат міністерство народної освіти який...
21095. Національне відродження 20-х рр. XX ст 24.41 KB
  громадянська війна в Україні закінчилася. Відомо що в період громадянської війни етнічні українці у більшовицькій партії в Україні складали тільки близько 1 . Тому політика коренізації здійснювалась у двох напрямах: українізації та створення необхідних політичних соціальних і економічних умов для культурного розвитку національних меншин. У цей час в Україні працював видатний педагог і письменник Антон Семенович Макаренко 18881939.