Е. А. Перминов методическая система обучения дискретной математике в аспекте интеграции образования монография

3.2.3.2. Редукция понятия изоморфных графов 

Необходимость редукции понятия изоморфных графов возника- 
ет при изучении многих технических дисциплин, где так или иначе 

чатных плат в радиотехнике, при проектировании различных управ- 
ляющих автоматов в электротехнике, систем энергоснабжения в элек- 

190 

Приведем типичный пример изложения этого важного понятия. 

которых 

V 
2 называются 
существует 

такая биекция φ (взаимно однозначное отображение φ) множества 

, что для любого ребра (v1, v2) ∈ E1 

V ′ , E ′ , изображенные 

(v1, v2) ∈ E1 справедливо (φvi, φvj) ∈ E ′ (1 ≤ i, j ≤ 4) при биекции 

v 
v 

′ 
v 
′ 
v 

v 
v 
′ 

′ 
v 
′ 
v 

′ 
′ 

1 
2 

Рис. 3.11 

Такой достаточно формальный подход к изложению понятия 

изоморфных графов, как правило, вызывает трудности при его вос- 

приятии студентами. Поэтому предложим следующую методическую 

редукцию этого понятия. 

Населенные пункты a, b, c, d (рис. 3.12) необходимо соединить 

дорогами так, чтобы существовал единственный маршрут, связываю- 

щий любые два пункта. Для этого рассмотрим графы, вершины кото- 

рых обозначают населенные пункты, ребра – дороги, их соединяю- 

щие. С помощью этих графов на рис. 3.13–3.24 изображены все воз- 

можные варианты прокладки дорог. Выбор того или иного варианта 

зависит от разных обстоятельств, например от стоимости каждой до- 

роги, соединяющей пункты. 

Представим сейчас, что буквы a, b, c, d обозначают сигнальные 

устройства системы электроснабжения. Требуется указать схему, 

191 

в которой радиосигнал, поступивший на одно из устройств, мог бы 

передаться единственным способом на все другие устройства. 

a b


a b

c d
c d

Рис. 3.12 
Рис. 3.13 Рис. 3.14 Рис. 3.15 Рис. 3.16