20508

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

Доклад

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

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

Украинкский

2013-07-25

27 KB

26 чел.

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

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

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

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

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

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

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

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

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

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

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

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

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


 

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

41890. Программы – архиваторы ОС MS-DOS (zip, arj,rar) и ОС семейства WINDOWS(winzip, winrar) 724.5 KB
  Функции архивирования и разархивирования встроены в файловую систему компьютера и доступны из программы «Проводник». На Вашем компьютере должна быть установлена одна из выше перечисленных программ-архиваторов. Обычно это WinRAR или WinZIP.
41891. Информатика и вычислительная техника. Информационные технологии и системы 92.45 KB
  Методические указания по выполнению лабораторных работ для студентов высших учебных заведений обучающихся по направлениям 230100 Информатика и вычислительная техника и 230200 Информационные технологии и системы Москва 2013 Оглавление Лабораторная работа № 1 Стандартные типы данных и выражения 3 Задание 1 3 Задание 2 4 Лабораторная работа № 2 Алгоритмизация линейных вычислительных процессов 10 Задание 1. 10 Задание 2. 10 Задание 3. 10 Задание 4.
41892. Структура документа и ввод данных. Лабораторные работы в MS Excel 2007 610.52 KB
  На втором листе книги расположите таблицу приведенную на рис. На третьем листе книги разместите таблицу приведенную на рис. Занесите информацию о расширениях файлов Excel в Office 2007 в табличную область первого листа книги и запомните эти расширения. После открытия окна "Microsoft Excel" активизируйте справочную систему (F1) и выберите в Обзоре справки Excel пункты Управление книгой – Управление файлами - Общие сведения о новых расширениях имен файлов и XML-форматов Office.
41893. Таблицы MS Excel 2007. Лабораторные работы в MS Excel 2007 403.81 KB
  Заполните диапазон А1:F10 данными по образцу приведенному на рис. Рис.а Рис. После преобразования в таблицу диапазон представлен на рис.
41894. Списки. Фильтрация данных. Связывание таблиц. Лабораторные работы в MS Excel 2007 1.43 MB
  Введите таблицу приведенную на рис. Рис. Введите таблицу представленную на рис. Активизируйте лист с исходной таблицей рис.
41895. ПРИНЦИПЫ ПРОГРАММНОГО УПРАВЛЕНИЯ ЭВМ. КОМАНДЫ MS DOS 683.51 KB
  В зависимости от варианта ответа DOS реагирует на возникшую ошибку поразному: аварийное завершение выполнения программы или команды выдавшей запрос; R повтор операции; F завершение выполнения операции и возврат кода ошибки; программа продолжает выполняться. Временный приостанов выполнения команды или программы например вывода информации на экран дисплея осуществляется нажатием клавиши Puse. Общие положения Тестовые программы используются для идентификации конфигурации компьютера его системных ресурсов а также для его диагностики...
41896. Emissions of combustive-lubricating materials stocks 32.01 KB
  146; Gross emissions: M=PT103 ton yer P emission per hour P is P1 or P2 T ctive time of source which cn be clculted for litting up: T=V p103 hour yer Where p= 300 m3 hour for gs; p=30 m3 hour for petrol; p=30 m3 hour for diesel fuel Min chrcteristics of wsters ccording to prgrph 17 of the lw On wstes producer determines composition nd chrcteristics of production wstes nd degree of their dnger for environment nd mn's helth. The dnger degree is coordinted with executive uthorities. Degree of dnger is chrcterized by the clss of...
41897. ДОСЛІДЖЕННЯ ПРОГРАМНОГО СЕРЕДОВИЩА РОЗРОБКИ ТА НАЛАГОДЖЕННЯ ПРИКЛАДНОГО ПРОГРАМНОГО ЗАБЕЗПЕЧЕННЯ СИСТЕМ КЕРУВАННЯ ТА ОБРОБКИ ІНФОРМАЦІЇ, ВИКОНАНИХ НА БАЗІ МІКРОПРОЦЕСОРІВ СІМЕЙСТВА MCS-51 2.48 MB
  Провести асемлеювання програми. Текст програми.1 ; надання імені vr_3 першому біту регістру RM 20H ; ; Програма ; ORG H ; адреса вектора розгалуження після початкового пуску RJMP _BEGIN ; мікропроцесора ; ORG H...