|
Лекция 1
Теоретико-множественное
введение
Это - не столько введение, сколько
напоминание некоторых терминов. Все они были в курсе по математической логике,
но нам они потребуются в несколько иных сочетаниях.
Итак, исходные неопределяемые
понятия: множество и элемент. Их надо
воспринимать интуитивно, на уровне жизненного опыта. Множество - это синоним
слова совокупность. Множество состоит из
элементов. Если a
- элемент множества A, то пишут  , а если a не является элементом множества A,
то пишут  . Символ   означает, что
множество A состоит из элементов  . Если нужно символически записать фразу «множество A состоит из элементов a, обладающих свойством f», то принято писать: .
Символ |A|
обозначает количество элементов во множестве A. Если
специально не оговорено иное, то все множества в наших рассмотрениях будут
конечными, т.е. такими, что  .
Если каждый элемент множества A
является элементом множества B, то говорят, что A
- подмножество B
и пишут  . Принято специальным термином и специальным символом
выделять множество, не содержащее ни одного элемента: его называют пустым множеством и обозначают символом  . Если одновременно и  , то множества A и B называются равными и пишут  . Над множествами можно проводить ряд традиционных действий.
А именно:
1.Объединение. Так называется множество C,
которое строится по заданным множествам A
и B следующим образом: в него включаются все
элементы из A и все элементы из B.
Обозначение: 
2.
Пересечение. Так называется множество
C, которое строится по заданным множествам A и B
следующим образом: в него включаются все элементы, принадлежащие одновременно
множеству A и множеству B.
Обозначение: 
3.Вычитание. Так называется множество C,
которое строится по заданным множествам A
и B следующим образом: в него включаются все
элементы из A, не принадлежащие множеству B.
Обозначение:  Часто при включении вместо  пишут  и говорят о дополнении подмножества B.
4. Произведение. Так называется множество C, которое
строится по заданным множествам A и B следующим
образом: в него включаются все упорядоченные пары  , где  . Обозначение:  Если , то  называется декартовым квадратом множества A;
подмножество всевозможных элементов  во множестве называется диагональю множества A
и обозначается  .
Напомним еще несколько определений.
Отношение на множестве. Если в декартовом квадрате некоторого множества A
выделено
какое-либо подмножество  , то говорят, что на A задано
отношение (или бинарное отношение). Если для некоторых
элементов  имеет место включение  , то говорят, что  находятся в отношении .
Если  , то отношение называется рефлексивным.
Если отношение  таково, что из
включения  обязательно следует,
что  , то отношение  называется симметричным.
Если отношение таково, что из
включений и  следует, что  , то отношение называется транзитивным.
Если отношение таково, что из
одновременных включений и следует, что  , то отношение называется антисимметричным.
Полагают по определению, что пустое
множество является отношением одновременно рефлексивным, симметричным,
антисимметричным и транзитивным.
Если отношение рефлексивно,
транзитивно и симметрично, то оно называ-ется эквивалентностью. Если же отношение одновременно рефлексивно,
транзитивно и антисим-метрично, то оно называется частичным порядком.
Если - частичный порядок на
множестве A и  , то говорят, что элементы  сравнимы относительно или просто сравнимы;
иногда пишут в этом случае  или просто  .
Лекция 2
Определение
графа. Вершины и ребра. Графическая интерпретация графа. Смежность и
инцидентность. Локальная степень. Подграф. Полный граф. Матрицы смежностей и
инциденций. Изоморфизм графов.
Пусть A - любое
множество. Обозначим через  множество всех неупорядоченных пар его различных
элементов. Например, если A={1,2,3}, то ={(1,2), (1,3), (2,3)}; если A={1,2}, то ={(1,2)}. Если A={1}, то  , так как различных элементов в A нет. Когда в
записи ={(1,2), (1,3), (2,3)} указывается пара (1,2),
подразумевается, что выражения (1,2) и (2,1) означают одно и то же: это и
означает, что пара неупорядочена,
т.е. не имеет значения, в каком порядке записаны элементы пары.
Графом
называется пара множеств  , где A - любое непустое множество, а B .
Элементы из A называются вершинами графа, а элементы из B - его ребрами. Вот пример графа:
Опишем
традиционную геометрическую интерпретацию
графа. Пусть - некоторый граф и  . Фиксируем на плоскости произ-вольным образом p
точек и произвольным образом
дадим им в качестве имен имена вершин данного графа; в итоге на плоскости
возникнут точки, обозначенные как  . Затем для каждой пары точек  таких, что  , проведем отрезок прямой, соединяющий точки . В результате таких действий возникнет некоторый рисунок,
который и называется
геометрической интерпретацией графа. Заметим, что одному и тому же графу
соответствует много рисунков, которые могут быть его геометрическими
интерпретациями.
Если в некотором графе , где  
 пара вершин такова, что , то вершины называются смежными; в этой ситуации каждая из них
называется инцидентной ребру  , а ребро называется инцидентным каждой из вершин . Если вершина  и ребро  инцидентны, то пишут  .
Количество ребер, инцидентных данной
вершине a называется ее степенью или локальной
степенью графа в вершине a; степень вершины a
обозначается через  . В приведенном выше примере степень вершины «1» равна 4,
степень вершины «2» равна 2, степень вершины «3» равна 3, степень вершины «4»
равна 2, степень
вершины «5»
равна 1. А вот пример графа с локальной степенью 0:  ; здесь вершина «3» имеет степень 0. Вершины со степенью 0
называются изолированными.
Можно проверить, что в любом графе количество вершин нечетной
степени обязатель-но четно.
Пусть теперь  - два графа таких, что
 и  ; тогда говорят, что  является подграфом графа  . Если в некотором графе множество ребер B
таково, что  , то граф называется полным.
Заметим, что если в полном графе число вершин равно p, то число ребер
равно  .
Пусть по-прежнему - граф и  - его вершины.
Построим квадратную матрицу  , положив
Очевидно, эта
матрца симметрична. Она называется матрицей
смежностей графа . В приведенном выше примере графа матрица смежностей такова:
 .
Сопоставим графу
еще одну матрицу.
Будем считать, что - по-прежнему
множество вершин и пусть   - множество ребер. Определим матрицу   следующим образом:
Введенная так
матрица N называется матрицей инциденций данного графа.
Очевидно, вид матрицы смежностей и
вид матрицы инциденций существенно зависят от того, как именно занумерованы
вершины и ребра. Если в приведенном выше примере графа считать, что
 ,
то матрица
инциденций будет такой:
 .
В каждом столбце
матрицы инциденций всегда ровно две единицы,
остальные
элементы равны нулю. Если в графе все вершины имеют
степень ноль, то
матрицы инциденций не существует.
Наконец, введем одно из важнейших
понятий в теории графов - понятие изоморфизма графов. Пусть - два графа.
Предположим, что существует такое отображение множеств вершин  , что выполнены следующие четыре условия:
1) если  , то  ;
2) для всякого  существует  такой, что  ;
3) если  , то  ;
4) для всякого  существует такое , что 
и  .
Тогда отображение f
называется изоморфизмом графов  , а сами эти графы называются изоморфными. Нетрудно заметить, что при изоморфизме каждая вершина
переходит в вершину с той же степенью. Поэтому наверняка неизоморфны графы, в
списке локальных степеней которых есть резкие отличия (например, в одном графе есть
вершина со степенью 3, а в другом такой степени вообще нет). Однако, проверка
двух графов на изоморфизм представляет собой намного более трудную задачу, чем
простое сравнение степеней.
|
