Лекции по "Математике"

Комбинируя  определения полного и симметрического  графов и полного и антисимметрического графов, получили следующие определения:

• граф G =(X, A), в котором любая пара вершин (х_i, х_j) соединена двунаправленными дугами, называется полным симметрическим (рис. 5.1,г);
• граф G =(X, A), имеющий для каждой пары вершин (х_i, х_j) только одну дугу, называется полным антисимметрическим или турниром.

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

 
Рис. 5.2.  Граф типа “дерево”: а – неориентированное дерево, б – ориентированное дерево

Ориентированное дерево представляет собой ориентированный  граф без циклов, в котором полустепень захода каждой вершины, за исключением одной (например, вершины х₁ ), равна 1, а полустепень захода вершины х₁ (называют корнем этого дерева) равна 0 (рис. 5.2,б).

Граф G =(X, A), который может быть изображен на плоскости или сфере без пересечений называется планарным (рис. 5.3).

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

На рис. 5.4 показаны непланарные графы. Эти два графа играют важную роль в теории планарных графов и известны как графы Куратовского.

 
Рис. 5.4.  Непланарные графы

Неориентированный граф G = (X, A)называют двудольным, если множество его вершин X может быть разбито на такие два подмножества X^а и X^b , что каждое ребро имеет один конец в X^а , а другой в X^b (рис. 5.5,а).

Ориентированный граф G называется двудольным, если его неориентированный двойник – двудольный граф (рис. 5.5,б,в).

Двудольный  граф G=(X^а X^b, A) называют полным, если для любых двух вершин х_i X^а и х_j X^b существует ребро (х_i,х_j) в G=(X,A) (рис. 5.5,г).

 
Рис. 5.5.  Двудольные графы: а, б, в – двудольные графы; г – полный двудольный граф

Для доказательства двудольности графа существует теорема.

Теорема о двудольности

Граф G = (X, A) является двудольным тогда и только тогда, когда он не содержит циклов нечетной длины.

Доказательство

1. Необходимость.  Поскольку множество X разбивается на две части X^а и X^b , то X^а X^b = X и X^а X^b = Ø .

Пусть существует цикл нечетной длины х_i1 , х_i2, ...,х_{i q} , х_i1 . Без потери общности допустим, что х_i1 X^а . Согласно определению одна из двух следующих друг за другом вершин этого цикла должна принадлежать множеству X^а , а другая – множеству X^b , тогда имеем: х_i2 X^b, х_i3 X^а и т. д. Следовательно, х_ik X^а , если k – нечетное, и х_ik X^b , если k – четное.

Мы предположили, что длина цикла нечетная. Поэтому  из соотношения х_{i q} X^а следует, что х_i1 X^b . Это противоречит исходному условию, поскольку X^а X^b = Ø и вершина не может принадлежать одновременно как X^a , так и X^b .

Для большей  ясности можно рассмотреть цикл нечетной длины для графа, изображенного  на рис. 5.6:

 

Задача  коммивояжера

1. Общее  описание

Задача  коммивояжера (в дальнейшем сокращённо - ЗК) является одной из знаменитых задач  теории комбинаторики. Она была поставлена в 1934 году, и об неё, как об Великую  теорему Ферма обламывали зубы лучшие математики. В своей области (оптимизации  дискретных задач) ЗК служит своеобразным полигоном, на котором испытываются всё новые методы.

Постановка  задачи следующая.

Коммивояжер (бродячий торговец) должен выйти из первого города, посетить по разу в  неизвестном порядке города 2,1,3..n и вернуться в первый город. Расстояния между городами известны. В каком  порядке следует обходить города, чтобы замкнутый путь (тур) коммивояжера был кратчайшим?

Чтобы привести задачу к научному виду, введём некоторые термины. Итак, города перенумерованы числами jÎТ=(1,2,3..n). Тур коммивояжера может быть описан циклической перестановкой t=(j₁,j₂,..,j_n,j₁), причём все j₁..j_n – разные номера; повторяющийся в начале и в конце j₁, показывает, что перестановка зациклена. Расстояния между парами вершин  С_ij образуют матрицу С. Задача состоит в том, чтобы найти такой тур t, чтобы минимизировать функционал                         

 

Относительно  математизированной формулировки ЗК уместно сделать два замечания.

Во-первых, в постановке С_ij означали расстояния, поэтому они должны быть неотрицательными, т.е. для всех jÎТ:                       

                      С_ij³0; C_jj=∞

(последнее  равенство означает запрет на  петли в туре), симметричными, т.е.  для всех i,j:                        

                        С_ij= С_ji.

и удовлетворять  неравенству треугольника, т.е. для  всех:                      

 С_ij+ С_jk³C_ik

В математической постановке говорится о произвольной матрице. Сделано это потому, что  имеется много прикладных задач, которые описываются основной моделью, но всем условиям (2)-(4) не удовлетворяют. Особенно часто нарушается условие (3) (например, если С_ij – не расстояние, а плата за проезд: часто туда билет стоит одну цену, а обратно – другую). Поэтому мы будем различать два варианта ЗК: симметричную задачу, когда условие (3) выполнено, и несимметричную - в противном случае. Условия (2)-(4) по умолчанию мы будем считать выполненными.

Второе  замечание касается числа всех возможных  туров. В несимметричной ЗК все туры t=(j₁,j₂,..,j_n,j₁) и t’=(j₁,j_n,..,j₂,j₁) имеют разную длину и должны учитываться оба. Разных туров очевидно (n-1)!.

Зафиксируем на первом и последнем месте в  циклической перестановке номер j₁, а оставшиеся n-1 номеров переставим всеми (n-1)! возможными способами. В результате получим все несимметричные туры. Симметричных туров имеется в два раз меньше, т.к. каждый засчитан два раза: как t и как t’.

Можно представить, что С состоит только из единиц и нулей. Тогда С можно интерпретировать, как граф, где ребро (i,j)  проведено, если С_ij=0 и не проведено, если С_ij=1. Тогда, если существует тур длины 0, то он пройдёт по циклу, который включает все вершины по одному разу. Такой цикл называется гамильтоновым циклом. Незамкнутый гамильтонов цикл называется гамильтоновой цепью (гамильтоновым путём).

В терминах теории графов симметричную ЗК можно сформулировать так:

Дана  полная сеть с n  вершинами, длина ребра (i,j)= С_ij. Найти гамильтонов цикл минимальной длины.

В несимметричной ЗК вместо “цикл” надо говорить “контур”, а вместо “ребра” - “дуги” или “стрелки”.

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

7. Математические  структуры: векторы и векторные  величины пространства

Величины, которые полностью определяются своим численным значением, называются скалярными. Примерами скалярных  величин являются: площадь, длина, объем, температура, работа, масса.

Другие  величины, например сила, скорость, ускорение, определяются не только своим числовым значением, но и направлением. Такие  величины называют векторными. Векторная  величина геометрически изображается с помощью вектора.

Вектор - это направленный прямолинейный отрезок, т. е. отрезок, имеющий определенную длину и определенное направление. Если А — начало вектора, а В - его конец, то вектор обозначается символом АВ или а. Вектор ВА (у него начало в точке В, а конец в точке A ) называется противоположным вектору АВ . Вектор, противоположный вектору а , обозначается -а .

Длиной или модулем вектора АВ называется длина отрезка и обозначается |АВ|. Вектор, длина которого равна нулю, называется нулевым вектором и обозначается 0 . Нулевой вектор направления не имеет.

Вектор, длина которого равна единице, называется единичным вектором и обозначается через e . Единичный вектор, направление которого совпадает с направлением вектора a , называется ортом вектора a и обо значается a °.

Векторы а и b называются коллинеарными, если они лежат на одной прямой или на параллельных прямых; записывают a ||b .

Коллинеарные  векторы могут быть направлены одинаково  или противоположно.

Нулевой вектор считается коллинеарным любому вектору.