Дискретка шпоры теоремылеммы

Обратн. Отнош. Для ∀ бинар. Отношений P,Q,R выполн:1)(P^-1)^-1=P ∆ ] (x,y) ϵP, тогда по опред-ию⇔ (y,x) ϵP^-1 ⇒ (x,y) ϵ(P^-1) ^-1 ⇒P=(P^-1) ^-1∆ 2) (P○Q) ^-1=Q^-1○ P^-1 ∆ ](x,y) ϵ(P○Q) ^-1⇒ (y,x) ϵ(P○Q) ⇒∃ z: (y,z)ϵP,(z,x) ϵQ⇒(x,z) ϵQ^-1, (z,y) ϵ P^-1⇒ (x,y) ϵ Q^-1○ P^-1 ⇒(P○Q) ^-1⊆ Q^-1○ P^-1 обратное-анал-но ⇒ (P○Q) ^-1=Q^-1○ P^-1 ∆ 3)(P○Q) ○R=P○(Q ○R) ∆ ](x,y) ϵ(P○Q) ○R⇒ ∃v:(x,v) ϵ(P○Q) ,(v,y) ϵR ⇒ ∃u: (x,u)ϵP,(u,v)ϵQ (v,y)ϵR ⇒ (x,u)ϵP, (u,y)ϵ(Q○R)⇒(x,y)ϵ(P○Q)○R ⇒(P○Q) ○RϵP○(Q ○R). включение в обр сторону – анал-но. (P○Q) ○R=P○(Q ○R) ∆

Св-ва функ-ий 1) if f:A↦B, g:B↦C ⇒f○g:A↦C ∆ if f:A↦B g:B↦C, f⊆AxB, g⊆BxC⇒ f○g⊆AxC (x,y)ϵf○g , причем xϵA yϵC ∃z ϵB: (x,z)ϵf ⇒ z=f(x) . (z,y)ϵg⇒ y=g(z). подставим: f○g(x)=y=g(x)=g(f(x)). ∆ 2)if f:A↦B id_A○f=f, f○id_A=f ∆очевидно∆ 3) if f:A(на)↦B, g:B(на)↦C ⇒f○g:A(на)↦C ∆ f○g- ∀ сϵС ∃ aϵA: c=f○g(a) т.к по условию g-сюръект.,то для ∀сϵС ∃bϵB,такой, что c=g(b). Т.к. отобр f –сюръект., то для ∀bϵB ∃aϵA,такой, что b=f(a). Итак, для ∀сϵС нашелся aϵA, что c=f○g(a) ∆ 4)if f,g-инъект. ⇒f○g – инъект. ∆ ] ∃ x₁,x₂ϵA, yϵC,что x₁ ≠ x₂,а (x₁,y) ϵf○g (x₂,y) ϵf○g ⇒ y=f○g(x₁) y=f○g(x₂) x₁ ≠ x₂ f-инъект. ⇒ f(x₁)≠f(x₂). f(x₁), f(x₂) ϵB и f(x₁)≠f(x₂), по усл. g-инъект. ⇒ g( f(x₁₎)≠g(f(x₂))⇒ f○g(x₁)≠f○g(x₂) ⇒ предположение неверно, такого y не ∃ ⇒ f○g-инъективное ∆ 5)if f:A↔B и g:B↔C, то f○g: A↔C ∆ следует из 3) и 4) ∆ 6) if f:A↔B ⇒ f ^-1:B↔A(f○f^-1=id_A,f ^-1○f=id_B) ∆Утверждение, что f ^-1 ∃,когда f– биекция следуют из опр-ия композиции. ∆

Теорема. A/E-разбиение мн-ва А. Если R- неко-ое разбиение мн-ва А, то можно задать соотв-щее ему отношение экви-ти Е по след. Правилу: xEy x,yϵA_i ∆первая часть ] E-отношение экв-тина мн-ве А, А/Е-фактор. Т.к. Е- это отнош экв-ти, это отнош рефлексивно ⇒ ∀xϵA xϵE(x) ⇒∀ эл-т мн-ва A/E – не пустой и A=UE(x) xϵA. Показать, что если E(x) ⋂E(y)= ∅,то E(x)=E(y). ] zϵE(x) ⋂E(y) ↓, uϵE(x) ↓ zϵ E(x) и zϵ E(y)↓ (x,u) ϵE↓ (x,z) ϵE и (y,z) ϵE⇒⇒⇒ (y,u) ϵE⇒uϵE(u) ⇒ E(x) ⊆E(y) включение в обр. сторону – аналогично E(x)=E(y). Вторая часть. ] E- отношение на мн-ве A, которое соотв-ет разбиению R. xEy ⇔ x,yϵA_i (надо показать рефл-ть и симм-ть). Рефл-ть и симм-ть очевидны. Транз-ть: берем xEy и yEz, тогда: x,yϵA_i и y,zϵA_j , где A_i,A_jϵR ⇒ yϵA_{i и} yϵA_j ⇒ A_i= A_j. x,zϵA_i ⇒xEz. Доказали транз-ть. Итого, это отнош-ие эквивал-ти. ∆

Теорема4. Если матрица смежности гр.G, то (i,j) элемент матр. A^K_G=A_G*…*A_G есть число (a_i,a_j)-маршрутов длины k. ∆ Индукцией по k. ] k=1,для k=1, маршрут длины 1 – дуга графа G. Теор док-на. Обозначим A^k-i_ij= α_ij A_ij=a_ij и пусть теор. Верна для k=i. Докажем, когда k=k. Эл. A^k_ij=(A^k-1A_ij)= ∑ⁿ_s=1α_isa_sj ⇒ α_isa_sj-кол-во маршрутов v_i к v_j длины k, где v_s – предпосл. вершина маршрута. ∑– число маршрутов длины k от v_i к v_j.

Теорема. Граф G- двудольный ⇔, когда X(G)=2. ∆ ] G – двудольный граф. окрасим вершины одной доли в один цвет; а другой доли – в другой цвет. Итак, никакие смежные вершины не окрашены одним цветом ⇒ X(G)=2. 2часть X(G)=2 обозн.через M₁ все вершины, окраш в один цвет. M₂- вершины в другой цвет. Т.к. между вершинами, имеющ одина цвет, нет ребер, то G – двудольный с долями M₁ иM₂. ∆

Теорема. В связном планарном графе имеет место соотношение p-q+r=2: ∆Методом мат. индукции по числу ребер. q=0 p=1 r=1 p-q+r=2 верно. ] соотношение верно для всех графов с q ребрами. Добавим еще ребро.1) Если добавл. ребро соедин. существ-ие вершины, то: q`=q+1 p`=p r`=r+1 p`-q`+r`=p+q+r=2 верно. 2) если Если добавл. ребро соедин. с новой вершиной: p`-q`+r = p-q+r=2 верно! ∆

Теорема. Код С с min расстоянием d_c может исправлять t ошибок, если d_c≥2t+1. ∆ обозначим B_t(x) – шар, радиусом t с центром в xϵF_qⁿ. B_t(x)={ yϵF_qⁿ|d(x,y) ≤t} Правило декодирования в ближ. кодовое слово гарантирует, что каждое полученное в рез-те передачи слова, содерж. не более t ошибок должно лежать в шаре, радуса t с центром в переданном кодовом слове. Для того, чтобы можно было исправить t ошибок, шары r=t с центром в кодовых словах не должны пересекаться. z ϵ B_t(x) z ϵ B_t(y) x,yϵC x ≠y. d(x,y) ≤ d(x,z) + d(z,y) ≤2t. По условию, d_c≥2t+1. противоречие. чтд.

Алгортм Форда Беллмана. 1шаг) задаем строку D⁽¹⁾=(d⁽¹⁾₁ ,.., d⁽¹⁾_n) d⁽¹⁾_i=0 d⁽¹⁾_j=ω_ij i≠ j. В этой строке d⁽¹⁾_j,если i≠ j, есть вес дуги (a_i,a_j), если ∃ и d⁽¹⁾_j=∞ если (a_i,a_j) ∉R 2шаг) строку D⁽²⁾=(d⁽²⁾₁ ,..,d⁽²⁾_n) d⁽²⁾_j=min{d⁽¹⁾_j,d⁽¹⁾_k+ω_kj } k=1,n d⁽²⁾_j- минимальный из весов (a_i,a_j) – маршрута, сост. из не более двух дуг. 3шаг) стоится D^(s)=(d^(s)₁ ,.., d^(s)_n) эл-т: d^(s)_j=min{d^(s-1)_j, d^(s-1)_k+ω_kj } k=1,n искомая строка взвешеного расс-ия получается при s=n-1, и эл-т d^(n-1)_j=ρ_ω(a_i,a_j) т.к. на этом шаге из весов всех (a_i,a_j) маршрутов содержащих не более n-1 дуг выбирается наименьший. А каждый маршрут с более чем -1 дугой содержит контур, добавление которого к маршруту не уменьшает взвеш-ое раст-ие, т.к предположили отсутствие контуров отр-ого веса. Работу алгоритма можно break, if D^(k)=D^(k+1).

Алгоритм Дейкстры. Этот алгоритм используется только для взвешенного графа, в котором веса всех дуг>0. ]G=<M,R> W=(ω_kj) ω_kj ≥0 a_i-выделенная вершина/источ-к. задаем строку D⁽¹⁾=(d⁽¹⁾₁ ,.., d⁽¹⁾_n), где d⁽¹⁾_i=0 d⁽¹⁾_j=ω_ij i≠ j T₁=M\{a_i} пусть на s–шаге уже опр-на строка D^(s)=(d^(s)₁ ,.., d^(s)_n) и мн-во вершин T_s cлед шаг: s+1. a_j ϵT_s такое: d^(s)_j=min{d^(s)_k/a_kϵT_s} и строим мн-воT_s+1: T_s+1= T_s\{a_i}. D^(s+1)=(d^(s+1)₁ ,.., d^(s+1)_n) заполняется: d^(s+1)_k=min{d^(s)_k,d^(s)_j+ω_kj } a_i ϵT_s+1. d^(s+1)_k= d^(s)_k. l=n-1 D^(n-1)-строка взвеш.расстояния между a_i и ост. вершин графа. d^(n-1)_j= ρ_ω(a_i,a_j).

Алгоритм нахождения кратчайшего пути в бесконтурном графе. ] G=<M,R>, M={ a₁ ,.., a_n}. Пусть в бесконтурном G выполняется условие: (a_i,a_j) i<j. Найдем ρ от a₁ до ост. вершин графа. Заполним: D⁽¹⁾=(d⁽¹⁾₁ ,.., d⁽¹⁾_n) d⁽¹⁾_i=0 d⁽¹⁾_j=ω_ij, j≥2 пусть на шаге s: D^(s)=(d^(s)₁ ,.., d^(s)_n) D^(s+1)=(d^(s+1)₁ ,.., d^(s+1)_n) d^(s+1)_k=min{d^(s)_k,d^(s)_j+ω_kj } k<j (a_k,a_j)ϵR этот – аналог алг.Форда Беллмана. Заканчивается на: s=n-1 d^(s-1)_k= ρ_ω(a₁,a_j).

Теорема про вершины. ∑ степеней(degs) всех вершин графа равно 2*q, где q- число ребер, n- число вершин.∑ ⁿ _i=1deg(a_i)=2*q ∆ степень вершины-кол-во ребер,кот. явл. верш. При суммировании всех степеней получаем, что каждое ребро считается дважды,т.к. оно инцидентно. Петли, по определению считаются дважды. ⇒ общая сумма=удоенному числу ребер. ∆

Теорема. Если связный граф, соедин. k-вершин нечетной степени, то min число, покрыв. его реберно-непересек степеней – k/2. ∆ ] G-связ. граф, кот. соедин. k вершин нечетн. степени. k-четное: ∑ ⁿ _i=1deg(a_i) – четное ∑ ^k _i=1deg(a_i) – четное. Рассмотрим G' получим добавлением к G нечетной вершины a и ребер, соед. вершину a со всеми верш. нечетной степени графа G, т.к. степени всех верш. G’ дают все ребра, инцидентн. a, то получится не больше k/2 цепей, содерж. все ребра графа G, т.е. покрыв графа G. С другой стороны, граф явл-ся объединением r-реберно-непересек. цепей,имеет не более 2*r вершин нечетной степени. Поэтому G нельзя покрыть цепями, число кот <k/3. ∆