Материал: baldin_kv_red_matematika_dlia_gumanitariev
С числами 
связано функциональное тождество, которое называется формулой бинома Ньютона
При а = 1 имеем
Пример 1.12. Используя бином Ньютона найти (1 + b)7.
1.3.Основытеорииграфов
Впервые термин “граф” был употреблен венгерским математиком Д. Кенигом в 19 6 г. Но начало теории графов было положено Л. Эйлером в 17 6 г., когда он решил задачу о кенигсбергских мостах и нашел критерий существования в графе специального маршрута (эйлерова цикла). Но как математическая дисциплина теория графов сформировалась именно в первой трети ХХ в. Эта теория располагает аппаратом решения различных прикладных задач из разных областей науки и техники, например, сетевое планирование и управление [10, 21]. В настоящее время теория графов — один из наиболее быстро развивающихся разделов математики.
Предположим, что V — это непустое конечное множество, а V(2) — это множество всех его двухэлементных подмножеств. Множество Е является произвольным подмножеством множес-
тва V(2), т. е. E # V(2).
Тогда графом (G) называется пара множеств (V, E), т. е. G = (V,E),гдеVG—множествовершинграфа,аEG—множество его ребер [10, 21, 25]. Любое ребро графа определяется парой его вершин. Если все пары вершин упорядоченные, то граф назы-
1
вается ориентированным (его ребра обозначают стрелками), в противном случае он — неориентированный. В том случае, если в графе есть ориентированные и неориентированные ребра, он называется смешанным. Ориентированный граф G можно задать как отношение, т. е. как подмножество прямого произведения множества его вершин V само на себя.
G # V V.
Вэтомслучаемножествовсехдвухэлементныхподмножеств V(2) заменяется декартовым произведением V V = V(2) [10].
Графы обычно изображаются в виде рисунков, на которых вершины изображаются кружками (точками), а ребра отрезка-
ми (рис. 1.12).
|
2 |
|
|
4 |
1 |
4 |
1 |
1 |
1 |
|
||||
|
|
|
|
2 |
5 |
|
|
4 |
|
|
|
|||
|
|
|
|
5 |
а) неориентирован- |
б) ориентированный |
в) смешанный граф |
||
ный граф |
|
граф |
|
|
|
|
|
Рис. 1.12 |
|
Приведем конкретный пример.
Пример 1.13. Пусть задано множество V={1,2, }. Тогда
V(2) = {(1,2), (1, ), (2, ), (1,1), (2,2), ( , ), (2,1), |
2 |
( ,1), ( ,2)}. |
|
Е = {(1,2), (1, ), ( ,2)}. |
1 |
Предположив, что порядок вершин |
|
имеет значение, получаем следующий ори- |
|
ентированный граф (рис. 1.1 ). |
Рис. 1.13 |
2
Далее вершины графа будем обозначать буквами V1, V2, V , …,Vn, а ребра e1, e2, …, em. Вообще говоря, две вершины Vi и Vj определяют ребро ek
т. е. ek = (Vi,Vj) (рис. 1.14).
И в этом случае они будут концевыми вершинами ребра ek. Но концевые вершины ребра не обязательно различны, т. е. начальная и конечная вершины могут совпадать. В этом случае ребро становится петлей (рис. 1.15).
Граф, имеющий петли, иногда называют псевдографом (рис. 1.16)
2
1
Рис. 1.16
Vi |
ek |
Vj |
|
||
|
Рис. 1.14 |
|
|
|
V2 |
V1 |
|
|
|
|
V |
4
Между двумя вершинами |
|
|
|
может проходить и несколько |
|
V1 |
|
ребер (ориентированных и не- |
|
||
V2 |
|
V |
|
ориентированных), их назы- |
|
||
|
|||
вают параллельными. А граф, |
|
|
|
имеющий такие ребра, называ- |
|
V4 |
|
ют мультиграфом (см. рис. 1.17). |
|
V5 |
|
Мультиграф — это пара (V, E), |
|
||
|
|
|
|
где V — множество вершин, а |
|
Рис. 1.17 |
|
Е — семейство подмножеств |
|
|
|
множества V(2). Употребление термина “семейство” говорит о том, что элементы множества V(2) могут повторяться (возможны параллельные ребра) [10].
Если граф не имеет петель и параллельных ребер его называют простым (см. рис. 1.1 ). Граф G называется графом порядка n, если он содержит n вершин. (На рис. 1.18 приведен граф восьмого порядка.) [21].
V1 |
V |
|
|
|
V7 |
V6 |
V |
2 |
|
|
|
V4 |
|
V8 |
V5 |
|
|
|
|
|
Рис. 1.18
Граф, который не имеет ребер (состоит только из вершин) называется пустым (рис. 1.19).
V1 |
V2 |
V4 |
V7 |
|
V |
V5 |
V6 |
|
|
Рис. 1.19 |
|
Граф, не имеющий вершин, называется ноль-графом ([). Две вершины называются смежными, если они являются кон-
цевыми вершинами какого-то ребра (например, вершины V1 |
и |
|||||
|
e1 |
|
|
V ; V2 и V7 на рис. 1.18). |
|
|
V1 |
V2 |
|
Если два ребра имеют общую |
|||
|
|
|||||
e2 |
e |
концевую вершину, то они являют- |
||||
|
|
|||||
|
|
ся смежными (например, ребра e1 |
и |
|||
e4 |
|
|
||||
|
|
e2; e2 и e4 на рис. 1.20). |
|
|||
|
V4 |
|
V |
|
||
|
|
Если имеют в виду разные эле- |
||||
|
|
|
|
|||
Рис. 1.20 |
менты графа (вершины и ребра), |
|
4
то используют понятия инцидентности, т. е. ребро инцидентно своим концевым вершинам (например, ребро e инцидентно
вершинам V2 и V ).
Число инцидентных вершине ребер называется степенью (валентностью) этой вершины и обозначается d(Vi). Например, степень вершины V2 равна (d (V2) = ) [10, 21, 27].
Вершина степени 1 называется висячей, вершина степени ноль — изолированной, а петля при вершине добавляет в степень этой вершины двойку.
V1 V V4
V2 |
V6 |
|
|
|
V5 |
Рис. 1.21
Например, вершина V4 на рис. 1.21 является висячей, а вершина V6 — изолированной, а степень вершины V1 равна 4 (dV1 = = 4, два ребра и петля).
Граф называют полным, если две любые его вершины смежные (см. рис. 1.1 ).
Приведем без доказательства две теоремы [10].
Теорема 1.1. Сумма степеней вершин графа равна удвоенному числу его ребер. У графа на рис. 1.21 имеется 7 ребер, а сумма степени его вершин равна — 14.
Теорема 1.2. Число вершин нечетной степени в любом графе четно. Например, у графа, изображенного на рис. 1.21 таких вершин две (V4 и V5).
Может оказаться, что один и тот же граф изображается разными рисунками. Говорят, что два графа G1 и G2 изоморфны, если существует такое взаимнооднозначное соответствие между множествами их вершин и ребер, что соответствующие ребра графов ицидентны соответствующим вершинам этих
5