Що таке гомоморфізм у графі?

Приклад 2.1. Для кожного дійсного числа c формула c(x + y) = cx + cy для всіх x і y в R говорить про те, що функція Mc : R → R, де Mc(x) = cx, є гомоморфізмом. Приклад 2.2. Для всіх дійсних чисел x і y |xy| = |x||y|.

Простий граф є ізоморфним іншому графу, якщо він містить біекційне відображення. На уроці були викладені деякі основні положення та властивості ізоморфізму. Простий граф є гомоморфним іншому графу, якщо він містить відображення.

Простими словами, Якщо інший граф G* можна сформувати шляхом поділу ребра G на додаткові вершини, або якщо граф G* можна отримати шляхом введення вершин ступеня 2 у будь-яке ребро графа G, то граф G* повний. Обидва графи G і G* відомі як гомеоморфні графи.

В алгебрі гомоморфізм – це відображення, що зберігає структуру, між двома алгебраїчними структурами одного типу (наприклад, дві групи, два кільця або два векторних простори). Слово гомоморфізм походить із давньогрецької мови: ὁμός (homos), що означає «однаковий» і μορφή (morphe), що означає «форма» або «форма».

Визначення. «Гомоморфізм — це застосування φ від графа G до графа H таке, що для всіх вершин u і v G, uv ∈ E(G) ⇒ φ(u)φ(v) ∈ E(H). Ми позначаємо існування гомоморфізму від G до H через G → H. Спосіб побачити гомоморфізм від G до H є.