Спец часть (часть 1) (3 поток) (2015) (by Кибитова) (1161601), страница 5
Текст из файла (страница 5)
По теореме Поста система функций {f0, f1, fS, fM, fL} полна. Рассмотрим функцию f0 (x1, …, xn) ∉ T0 (f0 (0, 0, …, 0) = 1). Возможны два случая: a) f0 (1, 1, …, 1) = 1 ⇒ f0 ∉ S ⇒ [f0, f1, fL, fM] = P2 и система {f0, f1, fL, fM} полна. b) f0 (1, 1, …, 1) = 0 ⇒ f0 ∉ M, T1 ⇒ [f0, fL, fS] = P2 и система {f0, fL, fS} полна. 12 Определение 1. Графом называется произвольное множество элементов V и произвольное семейство E пар из V. Обозначение: G = (V, E).В дальнейшем будем рассматривать конечные графы, то есть графы с конечным множеством элементов и конечным семейством пар.Определение 2. Если элементы из E рассматривать как неупорядоченные пары, то графназываетсянеориентированным,пары называютсярёбрами.Есличислаже элементыиз E рас2. Графы, деревья,планарныеа графы;их свойства.Оценкадеревьев.§15.Основные понятия теории графов.
Изоморфизм графов. Связность.сматривать как упорядоченные, то граф ориентированный, а пары — дуги.Определение1.3.ГрафомПара вида(a, a) называетсяпетлёй,если пара(a, b) встречаетсяв сеОпределениеназываетсяпроизвольноемножествоэлементовV и произвольмействе E несколько раз, то она называется кратным ребром (кратной дугой).ноесемейство E пар из V. Обозначение: G = (V, E).Определение 4. В дальнейшем условимся граф без петель и кратных рёбер называть неВ дальнейшем будем рассматривать конечные графы, то есть графы с конечным множеориентированным графом (или просто графом), граф без петель — мультиграфом, а мульством элементов и конечным семейством пар.тиграф, в котором разрешены петли — псевдографом.Определение 2.
Если элементы из E рассматривать как неупорядоченные пары, то графОпределение 5. Две вершины графа называются смежными, если они соединены ребром.называется неориентированным, а пары называются рёбрами. Если же элементы из E расОпределение 6. Говорят, что вершина и ребро инцидентны, если ребро содержит вершину.сматривать как упорядоченные, то граф ориентированный, а пары — дуги.Определение 7. Степенью вершины (deg v) называется количество рёбер, инцидентныхОпределение 3.
Пара вида (a, a) называется петлёй, если пара (a, b) встречается в седанной вершине. Для псевдографа полагают учитывать петлю дважды.мействе E несколько раз, то она называется кратным ребром (кратной дугой).Определение 4. В дальнейшем условимся граф без петель и кратных рёбер называть не2 5ориентированным графом (илипросто графом), граф без петель — мультиграфом, а муль1тиграф, в котором разрешены петли — псевдографом.Определение 5.
Две вершины графа называются смежными,8 если они соединены ребром.7Определение 6. Говорят, что вершина и ребро инцидентны, если ребро содержит вершину.Определение 7. Степенью вершины (deg v) называется количество рёбер, инцидентныхданной вершине. Для псевдографаполагают учитыватьпетлю дважды.43 6Глава II. Основы теории графов..25Утверждение 1. В любом графе (псевдографе) справедливо следующее соотношеp1.ние: ∑ deg vi = 2q , где p — число вершин, а q — число рёбер. 87=1iДоказательство. Когда мы считаем степень одной вершины, мы считаем все рёбра, выходящие из неё. Вычисляя сумму всех степеней, мы получаем, что каждое ребро считается43 6 (петли по определению степени также подважды, так как оно инцидентнодвум вершинамсчитаются дважды). Поэтому общая сумма будет равна удвоенному числу рёбер.
Утверждение Утверждениедоказано.1. В любом графе (псевдографе) справедливо следующее соотношеpОпределение 8. Пусть множество вершин графа V = {v1, v2, …, vp}. Тогда матрицейние:2q , гдеp —назовёмчисло вершин,числорёбер.смежностиграфаматрицуа Aq —= ||aaij = 1, если вершины vi и vj смежныij||, где∑ deg vi =этого(2, 3,i =1… для мультиграфа или псевдографа) и 0 в противном случае, aii при этом равно числуДоказательство.петельв вершине vi.
Когда мы считаем степень одной вершины, мы считаем все рёбра, выходящиеиз неё. Вычисляясумму (иливсех псевдографа)степеней, мы Gполучаем,что каждое ребро считаетсяОпределение9. Два графа1 = (V 1 , E 1 ) и G 2 = (V 2 , E 2 ) называютдважды,так как оноеслиинцидентнодвумдвавершинампо определениюстепенитакжепося изоморфными,существуютвзаимно(петлиоднозначныхотображенияφ1: V1 → V2 исчитаютсядважды).Поэтомуобщаясуммабудетравнаудвоенномучислурёбер.Утверждеφ2: E1 → E2 такие, что для любых двух вершин u и v графа G1 справедливо φ2 (u, v) =ние= (φдоказано.1 (u), φ1 (v)).Определениемножествовершин{v1, v2, …,vp}.
ТогдаматрицейОпределение 8.10Пусть(изоморфизмграфовбез графапетельV и= кратныхрёбер).Два графаG1 =смежностиэтогографаназовёмматрицуA=||a||,гдеa=1,есливершиныvиvijij существует взаимноi однозначноеj смежны= (V1, E1) и G2 = (V2, E2) называются изоморфными,если(2,3, … для мультиграфаили псевдографа)противномотображениеφ1: V1 → V2 такое,что (u, v) ∈ Eи1 0⇔в (φ(u), φ (v)) случае,∈ E2. aii при этом равно числупетельОпределениев вершине vi. 11. Граф G = (V , E ) называется подграфом графа G = (V, E), если111Определение 9. Два графа (или псевдографа) G1 = (V1 , E1 ) и G2 = (V2 , E2 ) называютV1взаимно⊆ V, E1 ⊆однозначныхE.ся изоморфными, если существуют дваотображения φ1 : V1 → V2 иφ2: E1 → E2 такие, что для любых двух вершин u и v графа G1 справедливо φ2 (u, v) == (φ1 (u), φ1 (v)).Определение 12.Путём в графеграфовG = (V, E)любая последовательность15 называетсяОпределение10 (изоморфизмбезпетель и кратныхрёбер).
Два графавидаG1 =v,(v,v),v,(v,v),…,v,(v,v),v.001112n–1n–1nn= (V1, E1) и G2 = (V2, E2) называются изоморфными, если существует взаимно однозначноеЧисло n в данныхназывается длиной пути.отображениеφ1: Vобозначениях1 → V2 такое, что (u, v) ∈ E1 ⇔ (φ (u), φ (v)) ∈ E2.Определение 13.путь, в котором нет повторяющихся рёбер.Определение11.ЦепьюГраф Gназывается1 = (V 1 , E 1 ) называется подграфом графа G = (V, E), еслиОпределение 14. Простой цепью называется путь без повторения вершин.V1 ⊆E. P — путь из v1 в v2. Тогда в P можноУтверждение 2.
Пусть в G = (V, E)v1 V,≠ vE2 1и⊆пустьвыделить подпуть из v1 в v2, являющийся простой цепью.Доказательство. Пусть данный путь — не простая цепь. Тогда в нём повторяется некоторая вершина v, то есть он имеет вид: P1 =15v0C1vC2vC3v2. Тогда он содержит подпуть P2 == v0C1vC3v2. Если в P2 повторяется некоторая вершина, то аналогично удалим ещё кусок иv0, (v0, v1), v1, (v1, v2), …, vn – 1, (vn – 1, vn), vn.Определение12.Путёмв0,графеE)…,называетсявидаvv1), v1G, (v=1,(V,vдлинойvпути., vn), vnпоследовательность.0, (v2),n – 1, (vn – 1любаяЧисло n в данных обозначенияхназываетсяv0, (v, v1), v1, (vпуть,v2), …,vn – 1, (vnнетЧислоОпределениеn в данных обозначенияхпути.0называется1,длиной– 1, vn), vn.13.
Цепьюназываетсяв которомповторяющихся рёбер.Определение13.Цепьюназываетсяпуть,вкоторомнетповторяющихсярёбер.Числоnвданныхобозначенияхназываетсядлинойпути.Определение 14. Простой цепью называется путь без повторениявершин.Определениецепью называетсяпуть безнетповторениявершин.рёбер.Определение 14.13. ПростойЦепью называетсяпуть, в которомповторяющихсяУтверждение 2. Пусть в G = (V, E) v1 ≠ v2 и пусть P — путь из v1 в v2. Тогда в P можноОпределение 2.14.
Простойцепьюпуть PбезУтверждениевG=(V, E)называетсяv1 ≠ v2 и пусть—повторенияпуть из v1 ввершин.v2. Тогда в P можновыделить подпуть из vПусть1 в v2, являющийся простой цепью.выделитьподпуть из2.v1Пустьв v2, являющийсяпростойцепью.УтверждениевG=(V,E)v≠vипустьP—путьизvв. Тогда в P можноДоказательство. Пусть данный путь 1— не2 простая цепь. Тогда в 1нёмv2повторяетсянекоДоказательство.данный путь — не простаявыделитьподпутьиз естьvПустьцепью.цепь. Тогда в нём повторяется неко1 в v2, являющийсятораявершинаv, тоон имеет вид: Pпростой1 = v0C1vC2vC3v2.
Тогда он содержит подпуть P2 =тораяДоказательство.вершина v, то есть он имеетвид:P1—= vнеон всодержитподпуть некоP =данныйпутьТогданёмповторяется0Cпростая1vC2vC3vцепь.2. Тогда= v0C1vC3v2. Если в P2 Пустьповторяетсянекотораявершина,тоаналогичноудалимещё кусок2 и=тораяv0C1vCv.ЕсливPповторяетсянекотораявершина,тоаналогичноудалимещёкусоквершинаv,тоестьонимеетвид:P=vCvCvCv.ТогдаонсодержитподпутьP2и=223 2так далее.3 Процессдолжензакончиться, так1 как0P11 —2конечныйпуть.
Утверждение доказано.такПроцессдолжензакончиться,так как Pпуть. Утверждениедоказано.= v0далее.CОпределениеповторяетсянекотораявершина,аналогичноудалим ещёкусок и1 — конечный1vC3v2. Если в15.P2Путьназываетсязамкнутым,если vто0 = vn.Определение15.Путь закончиться,называется замкнутым,еслиv=v.так далее.ПроцессдолжентаккакP—конечныйпуть.Утверждениедоказано.0n1 если он замкнут, и рёбра в нём неОпределение 16. Путь называется циклом,Определение16.ПутьПутьназываетсяназываетсяциклом, если vони рёбра в нём неОпределение15.замкнутым,0 = vзамкнут,n.повторяются.повторяются.Определение17.16.Путьназываетсяциклом,еслии рёбрав нём неОпределениеПутьназываетсяпростымциклом,еслионv =замкнут,v и вершиныне повторяются.Определение 17. Путь называется простым циклом, если v00 = vnn и вершины не повторяются.повторяются.Определение 18.
Граф G = (V, E) называется связным, если для любых вершин vi, vj ∈ VОпределение18. ПутьГрафназываетсяG = (V, E) простымназываетсясвязным,любых вершинvi, vj ∈ VОпределение 17.циклом,еслиеслиv0 = vдляне повторяются.n и вершины(vi ≠ vj) существует путь из vi в vj.(vi ≠ vОпределениеиз vi вGv=j. (V, E) называется связным, если для любых вершин vi, vj ∈ V18. Графj) существует путьРассмотрим отношение vi → vj существования пути из vi в vj.
Оноотношение(vi ≠ Рассмотримvj) существуетпуть из vivвi →v . v существования пути из vi в vj. Оно1) симметрично, так как(vji →j vj) ⇒ (vj → vi),1)симметрично,так какv(vРассмотримотношение→v vсуществованияi→j) ⇒ (vj → vi), пути из v в v . Оно2) транзитивно, так как (vi i → jvj) & (vj → vk) ⇒ (vi → vk), i j2)(vj(v→→vk)vi⇒1) транзитивно,симметрично,тактаккаккак(v(v→vjv) &)⇒), (vi → vk),i→3) рефлексивно, так как ∀i i(vi →j vi). j3)(vi →2) рефлексивно,транзитивно, так как ∀i(vi →vj) v&i).(vj → vk) ⇒ (vi → vk),Таким образом, получено, что vi → vj — отношение эквивалентности и множество вершинТакимобразом, получено,что(vvi i→→vvi).3) рефлексивно,так как ∀ij — отношение эквивалентности и множество вершинразбивается на конечное число классовэквивалентности: V → V1 ∪ V2 ∪ … ∪ Vk, Vi ∩ Vj = ∅ ⇐разбиваетсянаконечноечислоклассовэквивалентности:V → V1 ∪ V2 ∪ …и∪множествоVk, Vi ∩ Vj =∅⇐Таким образом, получено, что v → vj — отношение эквивалентностивершин⇐ i ≠ j.
При этом граф G разбивается iна связныеподграфы, которые называются компонентами⇐i ≠ j. При этомграф G разбиваетсяна связныеподграфы,Vкоторыеразбиваетсяна конечноечисло классовэквивалентности:→ V1 ∪ называютсяV2 ∪ … ∪ Vкомпонентамиk, Vi ∩ Vj = ∅ ⇐связности.связности.⇐ i ≠ j. При этом граф G разбивается на связные подграфы, которые называются компонентамиV1V2Vkсвязности.V1V2V1V2VkVk………Связные компоненты графа GСвязные компоненты графа GСвязные компоненты графа G§16. Деревья.Деревья.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
