Введение в теорию графов

Упражнение 1:

Номер 1

Найти прямые отображения для вершин х₁ и х₂ графа, показанного на рисунке

Ответ:

(1) Г⁺¹ (х₁) = {х₁, х₂, х₃, х₄}, Г⁺¹ (х₂) = {х₁, х₃ }

(2) Г⁺¹ (х₁) = { х₂, х₃, х₄}, Г⁺¹ (х₂) = {х₁, х₃ }

(3) Г⁺¹ (х₁) = { х₃, х₁, х₂}, Г⁺¹ (х₂) = {х₃, х₁ }

Номер 2

Найти прямые отображения для вершин х₃ и х₄ графа, показанного на рисунке

Ответ:

(1) Г⁺¹ (х₃) = {х₄, х₆ }, Г⁺¹ (х₄) = {х₅ }

(2) Г⁺¹ (х₃) = {х₄, х₆ }, Г⁺¹ (х₄) = {х₅, х₄}

(3) Г⁺¹ (х₃) = {х₁, х₂ }, Г⁺¹ (х₄) = {х₅, х₄}

Номер 3

Найти прямые отображения для вершин  х₅ и  х₆графа, 
показанного на рисунке

Ответ:

(1) Г⁺¹ (х₅) = {х₂ }, Г⁺¹ (х₆) = {х₁, х₅ }

(2) Г⁺¹ (х₅) = {х₂ }, Г⁺¹ (х₆) = {х₁, х₃ }

(3) Г⁺¹ (х₅) = {х₅ }, Г⁺¹ (х₆) = {х₁, х₅ }

Упражнение 2:

Номер 1

Найти обратные отображения для вершин х₃ и  х₄ графа, показанного на рисунке

Ответ:

(1) Г^-1 (х₃) = {х₆, х₄ }, Г^–1 (х₄) ={х₁, х₃ }

(2) Г^–1 (х₃) = {х₂, х₃ }, Г^–1 (х₄) ={х₁, х₃ , х₄}

(3) Г^–1 (х₃) = {х₁, х₂ }, Г^–1 (х₄) ={х₁, х₃ , х₄}

Номер 2

Найти обратные отображения для вершин  х₅и  х₆графа, показанного на рисунке

Ответ:

(1) Г^–1 (х₅) = { х₆, х₄}, Г^–1 (х₆) = { х₃ ,х₆ }

(2) Г^–1 (х₅) = { х₆, х₄}, Г^–1 (х₆) = { х₃},

(3) Г^–1 (х₅) = { х₆, х₄}, Г^–1 (х₆) = { х₆, х₄}

Номер 3

Найти обратные отображения для вершин  х₁и  х₂графа, показанного на рисунке

Ответ:

(1) Г^–1 (х₁) = { х₂ }, Г^–1 (х₂) = {х₅ }

(2) Г^–1 (х₁) = { х₁, х₂, х₆}, Г^–1 (х₂) = { х₁, х₅ }

(3) Г^–1 (х₁) = { х₂ , х₆}, Г^–1 (х₂) = {х₅ , х₁}

Упражнение 3:

Номер 1

Найти прямые многозначные отображения 4-го порядка для вершин  х₁ и  х₂ графа, показанного на рисунке

Ответ:

(1) Г⁺⁴(х₁) ={ х₁, х₂, х₃, х₄, х₅, х₆}, Г⁺⁴(х₂) ={ х₁,х₃, х₄, х₅, х₆}

(2) Г⁺⁴(х₁) ={ х₂, х₃, х₄, х₅, х₆}, Г⁺⁴(х₂) ={ х₁, х₂, х₃, х₄, х₅, х₆}

(3)

 Г⁺⁴(х₁) ={ х₁, х₂, х₃, х₄, х₅, х₆}, Г⁺⁴(х₂) ={ х₁, х₂, х₃, х₄, х₅, х₆}

Номер 2

Найти прямые многозначные отображения 2-го порядка для вершин  х₃ и  х₄ графа, показанного на рисунке

Ответ:

(1) Г⁺² (х₃) = {х₁, х₄, х₅}, Г⁺² (х₄) = { х₂, х₄, х₅, }

(2) Г⁺²(х₃) = { х₄, х₅}, Г⁺² (х₄) = { х₂, х₄, х₅, }

(3) Г⁺² (х₃) = {х₁, х₄, х₅}, Г⁺² (х₄) = { х₂, х₄ }

Номер 3

Найти прямые многозначные отображения 3-го порядка для вершин  х₅ и  х₆ графа, показанного на рисунке

Ответ:

(1) Г⁺³(х₅) ={ х₁, х₂, х₃, х₄, х₆}, Г⁺³(х₆) ={ х₁, х₂, х₃, х₄, х₅, х₆}

(2) Г⁺³(х₅) ={ х₁, х₂, х₃, х₄, х₆}, Г⁺³(х₆) ={ х₂, х₃, х₄, х₅, х₆}

(3) Г⁺³(х₅) ={ х₁, х₂, х₃, х₄, х₅, х₆}, Г⁺³(х₆) ={ х₁, х₂, х₃, х₄, х₅}

Упражнение 4:

Номер 1

Найти обратные многозначные отображения 3-го порядка для вершин  х₃и  х₄графа, показанного на рисунке

Ответ:

(1) Г^-3(х₃)={х₁, х₄ }, Г^-3(х₄) = {х₂, х₄ }

(2) Г^-3(х₃)={х₁, х₄ }, Г^-3(х₄) =

(3) Г^-3(х₃)={х₂, х₄ }, Г^-3(х₄) =

Номер 2

Найти обратные многозначные отображения 4-го порядка для вершин  х₁ и  х₂ графа, показанного на рисунке

Ответ:

(1) Г^-4 (х₁) = { х₂ ,х₅ }, Г^-4 (х₂) = {х₅ }

(2) Г^-4 (х₁) = { х₂}, Г^-4 (х₂) = {х₅ }

(3) Г^-4 (х₁) = { х₂}, Г^-4 (х₂) = {х₅ , х₁}

Номер 3

Найти обратные многозначные отображения 4-го порядка для вершин  х₅ и  х₃графа, показанного на рисунке

Ответ:

(1) Г^-4 ( х₅) ={ х₁, х₄ }, Г^-4 ( х₃)={х₂ , х₅ , х₁}

(2) Г^-4 ( х₅) ={ х₁, х₄ }, Г^-4 ( х₃)={х₂ }

(3) Г^-4 ( х₅) ={ х₁, х₄ }, Г^-4 ( х₃)={х₂ ,х₁ }

Упражнение 5:

Номер 1

Для графа, изображенного на рисунке найти прямые транзитивные замыкания для вершин  х₁и х₂,

Ответ:

(1) Т⁺(х₁) = { х₁, х₂, х₃, х₅, х₆}, Т⁺( х₂) ={ х₁, х₂, х₃, х₄, х₅, х₆}

(2) Т⁺(х₁) = { х₁, х₂, х₃, х₅, х₆}, Т⁺( х₂) ={ х₁, х₂, х₃, х₅, х₆}

(3)

 Т⁺(х₁) = { х₁, х₂, х₃, х₄, х₅, х₆},   Т⁺( х₂) ={ х₁, х₂, х₃, х₄, х₅, х₆}

Номер 2

Для графа, изображенного на рисунке найти прямые транзитивные замыкания для вершин х₃ и х₄

Ответ:

(1) Т⁺(х₁) = { х₁, х₂, х₃}, Т⁺( х₂) ={ х₁, х₂, х₃, х₅, х₆}

(2) Т⁺(х₁) = { х₁, х₃ }, Т⁺( х₂) ={ х₁, х₂, х₃, х₅, х₆}

(3) Т⁺(х₃) = { х₃}, Т⁺( х₄) ={ х₁, х₂, х₃, х₄, х₅, х₆}

Номер 3

Для графа, изображенного на рисунке найти прямые транзитивные замыкания для вершин  х₅и х₆,

Ответ:

(1) Т⁺(х₅) = { х₁, х₂, х₃, х₅, х₆}, Т⁺(х₆) = { х₆}

(2) Т⁺(х₅) = { х₁, х₂, х₃, х₅}, Т⁺(х₆) = { х₆}

(3) Т⁺(х₅) = { х₁, х₂, х₃, х₅, х₆}, Т⁺(х₆) = { х₁, х₂, х₆}

Упражнение 6:

Номер 1

Для графа, изображенного на рисунке найти обратные транзитивные замыкания для вершин  х₅и х₆,

Ответ:

(1) Т^-(х₅) ={ х₁, х₂, х₄}, Т^-(х₆) = { х₁, х₂, х₄, х₅, х₆}

(2) Т^-(х₅) ={ х₁, х₂, х₄, х₅ }, Т^-(х₆) = { х₁, х₂, х₄, х₅, х₆}

(3) Т^-(х₅) ={ х₁, х₂, х₄, х₅ }, Т^-(х₆) = { х₁, х₂, х₄, х₅}

Номер 2

Для графа, изображенного на рисунке найти обратные транзитивные замыкания для вершин  х₃ и х₄

Ответ:

(1) Т^-(х₃) = { х₃, х₂, х₄, х₁, х₅}, Т^-( х₄) ={ х₄ }

(2) Т^-(х₃) = { х₂, х₄, х₁, х₅}, Т^-( х₄) =⊕

(3) Т^-(х₃) = { х₃, х₂, х₄, х₁, х₅}, Т^-( х₄) = ⊕

Номер 3

Для графа, изображенного на рисунке найти обратные транзитивные замыкания для вершин  х₁ и х₂,

Ответ:

(1) Т^-(х₁) = { х₁, х₂, х₃, х₄, х₅ }, Т^-(х₂) ={ х₁, х₂, х₄, х₅ }

(2) Т^–(х₁) = { х₁, х₂, х₄, х₅ }, Т^-(х₂) ={ х₁, х₂, х₃, х₄, х₅ }

(3) Т^-(х₁) = { х₁, х₂, х₄, х₅ }, Т^-(х₂) ={ х₁, х₂, х₄, х₅ }

Введение в теорию графов - тест 3