Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Граф, вершина, ребро

Читайте также:
  1. ВСЯКИЙ, КОГО В ОДНО МГНОВЕНИЕ ПЕРЕБРОСИЛИ БЫ
  2. Всякий, кого в одно мгновение перебросили бы из Сибири в Сенегал, лишился бы чувств (Гумбольдт)
  3. ВСЯКИЙ, КОГО В ОДНО МГНОВЕНИЕ ПЕРЕБРОСИЛИ БЫ ИЗ СИБИРИ В СЕНЕГАЛ, ЛИШИЛСЯ БЫ ЧУВСТВ (ГУМБОЛЬДТ)
  4. Обзорную лекцию о мультимедиа прочитает Сергей Карпов, документальный фотограф, главный редактор проекта «Mediacrowd», куратор проекта «РУЛЕТ».
  5. Пагубность сребролюбия
  6. Седина в бороду - бес в ребро!

ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ

Единого общепринятого определения графа нет. В зависимости от решаемой задачи принимается то или иное определение, которые похожи, но это не одно и то же.

1736 год. Эйлер доказывает, что задача о Кёнигсбергских мостах не имеет решения. Центральная часть Калининграда – это два берега реки Перголя и два острова этой реки. Острова соединены между собой мостом и у одного острова 2+2 моста с берегами и у другого 1+1. Всего 7 мостов. Задача: обойти все четыре части суши – два берега и два острова, пройдя по каждому мосту по одному разу.

1930 год. Казимир Куратовский доказывает, что задача о трех домах и колодцах не имеет решения. Имеется три дома и три колодца. Нужно проложить тропика от каждого дома к каждому колодцу так, чтобы они не пересекались.

1976 год. Аппель и Хейкен с помощью компьютера, перебрав около 2000 контр-вариантов показали, что достаточно 4-ёх красок для раскраски карты. Карта – это разбивка поверхности не пересекающимися областями.

 

Граф, вершина, ребро

Под неориентированным графом (или короче графом) будем понимать такую произвольную пару G = <V, E>, что

.

Ориентированным графом (орграфом) будем называть такую произвольную пару G = <V, E>, что . В обоих случаях множества V и Е будем называть соответственно множеством вершин и множеством ребер графа G. Элементы множества Е для орграфа называются дугами

Граф G задается множеством точек или вершин х1, х2,..., хn, которое обозначается через X, и множеством линий или ребер a1, a2,..., an, которое обозначается символом A, соединяющих между собой все или часть этих точек. Таким образом,граф G полностью задается (и обозначается) парой (X, А).

Граф обычно изображается на плоскости в виде множества точек, соответствующих вершинам, и соединяющих их линий, соответствующих ребрам. Дуга в орграфе изображается линией со стрелкой, указывающей ориентацию дуги, т. е. направление от ее начала к концу

Линия, изображающая ребро {и, v}, или <и, v> ( угловые скобки используются для обозначения дуг орграфа. ), соединяет точки, изображающие вершины и, v причем во втором случае стрелка обозначает направление от и к v (рис. 1.1).

 

Рис. 1.1. а) Неориентированный граф; б) Ориентированный граф.

 


Дата добавления: 2015-07-07; просмотров: 120 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
МФА ОЦБНОЧНЫЙ ЛИСТ| Обратное соответствие

mybiblioteka.su - 2015-2024 год. (0.005 сек.)