Исследование алгоритмов решения задач дискретной математики

c) Cсимметрично, т.к. на пару <1.6> есть пара <6.1>

Рефлексивно, т.к. для найдется пара <x,x>. Например, <1,1>, <2,2>, <3,3> и т.д.;

Не  транзитивно, т.к. для пар <6,1> ,<1,6> не существует пара <6,6>;

Не  антисимметрично, т.к. есть симметричные пары

 

    Задание 7

«Служить  моделью» на множестве произвольных объектов;

не  рефлексивно т.к. X не может быть моделью сам для себя.

Не  симметрично т.к X является моделью для Y => Y не может являться моделью для X

транзитивно т.к X является модель для Y, а Y является моделью для Z следовательно X является моделью для Z

антисимметрично т.к есть только пары где X модель для Y.

   Теория  графов

   Задание 1

1. Ориентированный псевдограф D=(V,X). V={v₀,v₁,v₂,v₃,v₄,v₅}, X={x₀,x₁,x₂,x₃,x₄,x₅,x_6,x₇,x₈,x₉,x₁₀}. x₀=<v₁,v₄>, x₁=<v₀,v₂>, x₂=<v₂,v₄>, x₃=<v₂,v₃>, x₄=<v₃,v₅>, x₅=<v₅,v₅>, x₆=<v₅,v₄>, x₇=<v₅,v₄>, x₈=<v₃,v₁>, x₉=<v₁,v₂>, x₁₀=<v₁,v₀>.

 

2. X₅ – петля, x₆,x₇ – кратные ребра

 

3. Полустепени вершин: d⁺(v₀)=2, d^-(v₀)=1, d⁺(v₁)=2, d^-(v₁)=1, d⁺(v₂)=2, d^-(v₂)=2, d⁺(v₃)=2, d^-(v₃)=1, d⁺(v₄)=0, d^-(v₄)=4, d⁺(v₅)=3, d^-(v₅)=2

    

     4.Матрица смежности

Матрица инцидентности

 
 

Матрица связности:

 

Матрица достижимости:

 
 

5. Простой цикл: V₀X₁V₂X₃V₃X₈V₁X₁₀V₀   V₁X₉V₂X₃V₃X₈V₁

Цикл: нет циклов

   Простая цепь : V₀X₁V₂X₂V₄

   Цепь: V₀X₁V₂X₃V₃X₄V₅X₅V₅

   Задание 2

 

2. Неориентированный граф G=(V,X). V={v₀,v₁,v₂,v₃,v₄,v_5, v₆}, X={x₀,x₁,x₂,x_3,x₄,x₅,x_6,x₇,x₈}. x₀={v₀,v₀}, x₁={v₀,v₂}, x₂={v₀,v₃}, x₃={v₃,v₁}, x₄={v₄,v₁}, x₅={v₁,v₅}, x₆={v₂,v₄}, x₇={v₄,v₆}, x₈={v₃,v₃}.

 

3. v₅ и v₆– висячие вершины.

 

4. Степени вершины 

d(v₀)=3, d(v₁)=3, d(v₂)=2, d(v₃)=3, d(v₄)=3, d(v₅)=1, d(v₆)=1. 

Матрица смежности

Матрица инцидентности