20508

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

Доклад

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

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

Украинкский

2013-07-25

27 KB

29 чел.

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

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

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

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

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

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

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

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

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

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

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

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

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


 

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

81645. Буду я природі другом 86.5 KB
  Мета: поглиблювати навички роботи над різними жанрами творів; розвивати способи і види читання; виховувати бережливе ставлення до природи. II Мовна розминка Учитель Урок з читання почнемо без зупинки з артикуляційної розминки 1. Скоромовка Читання скоромовки дощиком Жовте жито жук жував і з Женею жартував.
81646. Підсумковий урок з теми «Оповідання» 315.5 KB
  Вчити аналізувати та оцінювати поведінку та вчинки дійових осіб, робити висновки щодо прочитаного, поглибити знання дітей про загальнолюдські моральні якості. Розвивати навички читання, зв’язне мовлення, вміння висловити свою думку, цінувати думки товаришів.
81647. Бабусина пригода 73.5 KB
  Мета: Ознайомити дітей із п’єсою,як літературним жанром;вдосконалювати навички виразного читання; вчити інсценувати п’єсу засобами лялькового театру; вчити характеризувати дійових осіб. Розвивати творчі здібності учнів. Розвивати комунікативні (уміння формулювати і доводити власну думку; розвивати культуру мовлення)...
81648. Марійка Підгірянка «Співанка про місяці», «Діти й ластівка». Загадка 191.5 KB
  Мета: збагачувати та розширювати знання учнів про життєвий і творчий шлях Марійки Підгірянки; розвивати мовлення учнів; виховувати любов до природи і рідного слова. Обладнання: портрет поетеси, збірки її творів, мультимедійна дошка, ілюстра ції до творів, презентація до уроку.
81649. В. Сухомлинський «Хлопчик і Дзвіночок Конвалії» 77 KB
  Подивіться, будь ласка, мабуть немає людини, байдужої до чарівної краси цих ніжних, витончених, дуже ароматних квітів. Наче якісь зачаровані сріблясті дзвіночки, повисають вони на зелених струнких ніжках посеред зеленого листя.
81650. Осінні мотиви в поезії Ліни Костенко 52 KB
  Обладнання: таблиці Шульте картки для читання карткилисточки зі словами робочий зошит зоровий диктант Хід уроку І. Читання віршів напамять. Учитель виразно у повільному темпі читає текст а потім запитує: Чи сподобався вам вірш Який настрій у вас після його слухання Підготовка до читання тексту.
81651. В.Нестайко «Жевжик» 72.5 KB
  Всеволод Зіновійович Нестайко народився на Житомирщині. Тож все своє свідоме життя Всеволод Нестайко прожив у Києві. Нестайка була вчителькою Коли Всеволод Нестайко був маленьким хлопчиком він страшенно хотів швидше вирости і стати великим та дорослим.
81652. «Коли тобі сутужно – прийде на поміч дружба А. Костецький «Буває все...», «Краще — з друзями разом!», «Словник Славка» 58.5 KB
  Удосконалювати вміння виразно читати вірші визначати головну думку прочитаного; розвивати мовлення учнів уміння аналізувати віршовані твори виділяти головне висловлювати оцінні судження збагачувати словниковий запас; виховувати почуття товариськості.
81653. Поетичні картини ранньої і пізньої осені в творах Ліни Костенко 37.5 KB
  Книга природи – наймудріша книга. Спілкування з природою дає нам радість. Природа – це джерело краси, яка не може залишити байдужою навіть найнезворушливішу людину. Не випадково багато видатних мислителів і письменників, художників і поетів, зодчих і композиторів прагнули втілити у своїх творах нетлінну красу природи.