Методические указания по выполнению самостоятельных работ Дисциплина «дискретная математика»

КОНТРОЛЬНАЯ РАБОТА № 2

1. Вариант 1

1. 
   Для орграфа G₀ (рис. 1) найдите множество достижимости и множество контрдостижимости вершины х1. Выясните, какими свойствами обладает бинарное отношение, заданное графом G₀. Постройте матрицу смежности и матрицу инцидентности, занумеровав дуги орграфа G₀.
   
2. 
   Занумеруйте вершины графа G₁ (рис. 1) и определите степени всех его вершин. Нарисуйте какой-либо остовный подграф графа G₁. Запишите матрицу смежности и матрицу инцидентности графа G₁, занумеровав его ребра.
   
3. 
   Покажите, что графы G₁и G₂ (рис. 1) изоморфны. Планарен ли граф G₂?
   
4. 
   Определите цикломатическое число графа G₁ (рис. 1). Выясните, можно ли нарисовать граф G₁, не отрывая руки от бумаги и не проходя ни по одному ребру дважды. Ответ обоснуйте.
   
5. 
   Выясните, сколько ребер нужно удалить из графа G₁ (рис. 1) при построении его каркаса. Занумеруйте вершины графа G₁ и постройте каркас двумя способами (обход «в ширину», обход «в глубину»), начав обход из вершины с максимальной степенью.
   

1. Вариант 2

1. 
   Для орграфа G₀ (рис. 2) найдите множество достижимости и множество контрдостижимости вершины х1. Выясните, какими свойствами обладает бинарное отношение, заданное графом G₀. Постройте матрицу смежности и матрицу инцидентности, занумеровав дуги орграфа G₀.
   
2. 
   Занумеруйте вершины графа G₁ (рис. 2) и определите степени всех его вершин. Нарисуйте какой-либо остовный подграф графа G₁. Запишите матрицу смежности и инцидентности графа G₁, занумеровав его ребра.
   
3. 
   Покажите, что графы G1и G2 (рис. 2) изоморфны. Планарен ли граф G2?
   
4. 
   Определите цикломатическое число графа G1 (рис. 2). Выясните, можно ли нарисовать граф G₁, не отрывая руки от бумаги и не проходя ни по одному ребру дважды. Ответ обоснуйте.
   
5. 
   Выясните, сколько ребер нужно удалить из графа G₁ (рис. 2) при построении его каркаса. Занумеруйте вершины графа G₁ и постройте каркас двумя способами (обход «в ширину», обход «в глубину»), начав обход из вершины с максимальной степенью.
   

1. 
   
   жүктеу/скачать 410 Kb.
   
   Достарыңызбен бөлісу: