Понедельник, 21.09.2020, 21:47
Ш  К  О  Л  А     П  И  Ф  А  Г  О  Р  А
      Предмет математики настолько серьезен, что нужно
не упускать случая, сделать его немного занимательным".
                                                                           Блез Паскаль
Главная | Регистрация | Вход Приветствую Вас Гость | RSS
ПАМЯТКИ ПО МАТЕМАТИКЕ   ВЕЛИКИЕ МАТЕМАТИКИ   ТЕОРИЯ ЧИСЕЛ   МАТЕМАТИЧЕСКАЯ ЛОГИКА
УРОКИ МАТЕМАТИКИ В ШКОЛЕ


МАТЕМАТИЧЕСКАЯ КЛАДОВАЯ


В МИРЕ ЗАДАЧ
ЕГЭ ПО МАТЕМАТИКЕ
МАТЕМАТИКА В НАЧАЛЬНОЙ ШКОЛЕ
ВАРИ, КОТЕЛОК!
УДИВИТЕЛЬНАЯ МАТЕМАТИКА
ВЫСШАЯ МАТЕМАТИКА
В МИРЕ ИНТЕРЕСНОГО
Категории раздела
ПРОСТЫЕ ЧИСЛА. ДОЛГАЯ ДОРОГА К БЕСКОНЕЧНОСТИ [37]
КОГДА ПРЯМЫЕ ИСКРИВЛЯЮТСЯ. НЕЕВКЛИДОВЫ ГЕОМЕТРИИ [23]
МУЗЫКА СФЕР. АСТРОНОМИЯ И МАТЕМАТИКА [57]
МАГИЯ ЧИСЕЛ. МАТЕМАТИЧЕСКАЯ МЫСЛЬ ОТ ПИФАГОРА ДО НАШИХ ДНЕЙ [27]
ИНВЕРСИЯ [20]
ИСТИНА В ПРЕДЕЛЕ. АНАЛИЗ БЕСКОНЕЧНО МАЛЫХ [47]
БЕСКОНЕЧНОСТЬ В МАТЕМАТИКЕ [43]
МАТЕМАТИЧЕСКАЯ ЛОГИКА И ЕЕ ПАРАДОКСЫ [6]
ИЗМЕРЕНИЕ МИРА. КАЛЕНДАРИ, МЕРЫ ДЛИНЫ И МАТЕМАТИКА [33]
АБСОЛЮТНАЯ ТОЧНОСТЬ И ДРУГИЕ ИЛЛЮЗИИ. СЕКРЕТЫ СТАТИСТИКИ [31]
КОДИРОВАНИЕ И КРИПТОГРАФИЯ [47]
МАТЕМАТИКА В ЭКОНОМИКЕ [39]
ИСКУССТВЕННЫЙ ИНТЕЛЛЕКТ И МАТЕМАТИКА [35]
ЧЕТВЕРТОЕ ИЗМЕРЕНИЕ. ЯВЛЯЕТСЯ ЛИ НАШ МИР ТЕНЬЮ ДРУГОЙ ВСЕЛЕННОЙ? [9]
ТВОРЧЕСТВО В МАТЕМАТИКЕ [44]
ЗАГАДКА ФЕРМА. ТРЕХВЕКОВОЙ ВЫЗОВ МАТЕМАТИКЕ [30]
ТАЙНАЯ ЖИЗНЬ ЧИСЕЛ. ЛЮБОПЫТНЫЕ РАЗДЕЛЫ МАТЕМАТИКИ [95]
АЛГОРИТМЫ И ВЫЧИСЛЕНИЯ [17]
КАРТОГРАФИЯ И МАТЕМАТИКА [38]
ПОЭЗИЯ ЧИСЕЛ. ПРЕКРАСНОЕ И МАТЕМАТИКА [23]
ТЕОРИЯ ГРАФОВ [33]
НАУКА О ПЕРСПЕКТИВЕ [29]
ЧИСЛА - ОСНОВА ГАРМОНИИ. МУЗЫКА И МАТЕМАТИКА [15]
Статистика

Онлайн всего: 5
Гостей: 5
Пользователей: 0
Форма входа

Главная » Файлы » МИР МАТЕМАТИКИ » ТЕОРИЯ ГРАФОВ

Азы теории графов
20.01.2016, 20:43
Граф определяется множеством точек (которые также называются вершинами, или узлами графа) и множеством ребер, или дуг графа, которые соединяют его вершины попарно.


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



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

Графы также можно представить в виде списков, таблиц и различных выражений. Вершины графа можно изобразить в виде точек, окружностей, треугольников, а ребра — в виде прямых отрезков или фигурно изогнутых линий. Учитывая подобное разнообразие, важно уметь определять, когда два представления графа являются эквивалентными (изоморфными). Эквивалентные представления графа содержат одинаковые вершины и одинаковые связи между ними. Иными словами, между вершинами и ребрами двух представлений должно существовать взаимно однозначное соответствие, такое что степени вершин в обоих случаях будут одинаковы.

Три следующие фигуры — это три разных представления одного и того же графа. Согласитесь, увидеть это не так-то просто!



На рисунках ниже изображены четыре графа — (а), (Ь), (с) и (d). Граф (а) является исходным, остальные три — его подграфы. Это означает, что в них были выбраны лишь некоторые ребра и вершины исходного графа. Подграфы позволяют изучать графы по частям.



Обычно различают три типа графов: обыкновенные графы, мультиграфы и псевдографы. На рисунках ниже слева направо представлены все три типа графов.



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

Применительно к различным вариантам обхода графа используются следующие обозначения. Пусть G — помеченный граф с вершинами V0, V1, V2,. и ребрами X1, Х2, Х3, … Тогда маршрутом в графе будет называться конечная последовательность вида V0, X1, V1,., Vn-1, Xn, Vn, в которой чередуются ребра и вершины. Запись вида (V0, V1, …, Vn) подразумевает, что любые две вершины соединяются только одним ребром, и маршрут определяется указанной последовательностью вершин. Если V0 = Vn, то есть исходная и конечная вершина маршрута совпадают, то маршрут является замкнутым, иначе — открытым. Путь — это маршрут, в котором каждое ребро проходится только один раз. Замкнутый маршрут, содержащий п разных вершин, называется циклом. Обратите внимание, что любой цикл можно представить графически в виде многоугольника, что будет показано позже.

* * *

ГРАФЫ И ГРАФИКИ

Граф. Это слово может означать «пишу» («графология», «графомания», «телеграф»), а в случае теории графов обозначает множество точек и линий между ними. Не следует путать графы и графики. Да, можно заметить, что в графиках линейных функций, образованных прямыми линиями или последовательностью отрезков, соединяющих точки, фактически каждой точке х оси ОХ сопоставлена точка (х, f(x)) на графике функции. Это выполняется и в классических графиках функций, построенных в декартовых координатах с двумя осями X и Y, на которых отмечаются точки (х, f(x)), образующие график функции у = f(х). Тем не менее это множество точек и линий нельзя назвать графом.

Графы обычно используются для представления отношений между элементами конечного множества. Например, чтобы представить отношения эквивалентности, позволяющие разделить элементы множества на классы, «точками» графа изображают элементы множества и соединяют «линиями» связанные или эквивалентные элементы (если элемент связан сам с собой, то на графе образуется петля). Отношения порядка изображаются с помощью ориентированных графов. Дуги со стрелками означают отношение «меньше, чем». Связь теории графов и теории множеств более подробно объясняется в Приложении.

* * *



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



В приведенных выше двух примерах на рисунке слева изображен связный граф, на рисунке справа — несвязный.

* * *

ГРАФЫ И ЧИСЛА

Если две вершины графа могут соединяться не более чем одним ребром, то такой граф можно выразить таблицей чисел, или матрицей. Связный граф ABCDE, изображенный на рисунке, можно представить в виде следующей таблицы. Если соответствующие вершины соединены ребром, в ячейке записывается 1, если нет — 0.



ПЕРЕДАЧА СООБЩЕНИЙ И ОШИБКИ

В 1956 году Клод Шеннон, создатель теории информации, занялся проблемами передачи сообщений по каналам связи, где сигнал может искажаться. В подобных задачах канал связи представляется в виде графа: его вершины соответствуют символам сообщения, а ребра соединяют вершины, соответствующие символам, которые можно перепугать между собой при передаче данных.

Категория: ТЕОРИЯ ГРАФОВ | Добавил: admin | Теги: ИТК и мате, Мир Математики, искусственный интеллект, машинное обучение, популярная математик, математика и информатик, дидактический материал по матем
Просмотров: 1162 | Загрузок: 0 | Рейтинг: 0.0/0
УЧИТЕЛЮ ИНФОРМАТИКИ
КОНСПЕКТЫ УРОКОВ
ВНЕКЛАССНЫЕ МЕРОПРИЯТИЯ ПО ИНФОРМАТИКЕ
ПОСОБИЯ И МЕТОДИЧКИ ДЛЯ УЧИТЕЛЯ ИНФОРМАТИКИ
ИЗ ОПЫТА РАБОТЫ УЧИТЕЛЯ ИНФОРМАТИКИ
ЗАДАНИЯ ШКОЛЬНОЙ ОЛИМПИАДЫ ПО ИНФОРМАТИКЕ


ИНФОРМАТИКА В ШКОЛЕ


ИНФОРМАТИКА В НАЧАЛЬНЫХ КЛАССАХ
ИНФОРМАТИКА В 3 КЛАССЕ
ИНФОРМАТИКА В 4 КЛАССЕ
КОНТРОЛЬНЫЕ РАБОТЫ ПО ИНФОРМАТИКЕ. 3 КЛАСС
КОНТРОЛЬНЫЕ РАБОТЫ ПО ИНФОРМАТИКЕ. 4 КЛАСС
ПРОГРАММИРОВАНИЕ ДЛЯ ДЕТЕЙ
СКАЗКА "ПРИКЛЮЧЕНИЯ ЭЛЕКТРОШИ"
ИГРОВЫЕ ТЕХНОЛОГИИ НА УРОКАХ ИНФОРМАТИКИ
ВИКТОРИНЫ ПО ИНФОРМАТИКЕ
КОМПЬЮТЕРНЫЕ ЧАСТУШКИ
ОБРАТНАЯ СВЯЗЬ
Поиск


Друзья сайта
  • Создать сайт
  • Все для веб-мастера
  • Программы для всех
  • Мир развлечений
  • Лучшие сайты Рунета
  • Кулинарные рецепты

  • Copyright MyCorp © 2020
    Яндекс.Метрика Рейтинг@Mail.ru