ЛЕКЦИЯ 17

Контрольные вопросы

  1. Что называется соответствием между двумя множествами?
  2. Какое соответствие называется всюду определенным?
  3. Какое соответствие называется частично определенным? В каком случае соответствие называется функциональным?
  4. Каким условиям должно отвечать взаимнооднозначное соответствие?
  5. Что называется функцией?
  6. Какая функция называется отображением?
  7. В каком случае отображение называется отображением А в В, и в каком случае- А на В?
  8. В каком случае для функции существует обратная?
  9. Какая функция называется инъективной?
  10. Какая функция называется сюръективной?
  11. Какая функция называется биективной?
  12. Что такое композиция двух функций. Какими свойствами обладает композиция двух функций?
  13. Сформулировать теорему о существовании обратного отображения.
  14. Составить всевозможные композиции из функций f(x) = lgx и g(x) = sinx. Проверить композиции на биективность.
  15. Составить для функций обратные соответствия и проверить являются ли они функциями: а). ; б).

 

 

ТЕМА: НЕОРИЕНТИРОВАННЫЙ ГРАФ.

ПЛАН:

1. Основные понятия

2. Смежность, инцидентность. Степени вершин

3. Способы задания графов

4. Маршруты в неориентированном графе

5. Операции над графами

6. Связность. Компоненты связности

Главная

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

Развитие теории графов стимулируется ее большим прикладным значением. Особенно широкое применение теория графов нашла в технике. Без нее не возможна разработка современных систем автоматизированного управления и проектирования.

 

1. Основные понятия .

 

Определим понятие конечного графа. Представим себе на плоскости некоторое конечное множество точек V и конечный набор линий Х, соединяющих некоторые пары точек из V. Такой геометрической конфигурацией (диаграммой) описывается , например, схема автомобильных дорог, связывающих города некоторой области, или экономические связи между предприятиями и т.д..

При решении многих задач, не существенно связаны ли точки отрезками или криволинейными дугами. Важно лишь то, что каждая линия соединяет какие- либо две из заданного набора точек.

При рассмотрении задач теории графов ограничиваются исследованием совокупности двух конечных множеств V и Х. Элементы множества V называются вершинами графа, а элементы множества Х – ребрами.

Сформулируем определение неориентированного графа:

Непустое множество V = {v1, v2,…,vn} и набор Х пар объектов {vi, vi+1}, где viÎV, vi+1ÎV, называется графом.

Т.к. V и Х конечные множества, то граф называется конечным.

Если пара упорядоченная (vi, vi+1), граф называется ориентированным и обозначается D(V,X).

Если пара неупорядоченная {vi, vi+1}, то граф называется неориентированным и обозначается G(V,X).

Рассмотрим сначала неориентированные графы.

Как было сказано выше граф изображается диаграммой на плоскости. Приведем пример:

 

 

Рис. 13.1

 

В данном графе есть пара с одинаковыми вершинами {v3, v3}. Ребро соответствующее такой паре называется петлей.

Граф также содержит одинаковые пары {v6, v5}. Такие пары называются кратными ребрами. Количество одинаковых пар, соответствующих вершинам vi и vi+1 называется кратностью ребра. В приведенном примере кратность ребра {v6, v5} равна двум.

Граф, содержащий кратные ребра и петли называется псевдографом (рисунок 13.1).

Псевдограф без петель называется мультиграфом (рисунок 13.2).

Мультиграф без кратных ребер называется простым графом (13.3).

 

Рис. 13.2. Мультиграф. Рис. 13.3. Граф.

 

 

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

 

Рис. 13.4. Полный граф.