Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Задание. 1. Выбрать произвольные два графа G =(V , E ) и G = (V , E ) с заданным числом вершин и ребер (в соответствии с номером в журнале)
|
|
1. Выбрать произвольные два графа G 
=(V , E ) и G 
= (V , E ) с заданным числом вершин и ребер (в соответствии с номером в журнале), имеющие не менее двух общих вершин.
2. Для данных графов G 
=(V , E ) и G = (V , E ) построить графы: 
− дополнение графа G 
, G 
− получен из G удалением вершины i, G 
− получен из G удаление ребра (i, j), G 
G , G 
G , G + G .
2. Для результирующих графов, полученных в результате операций дополнения, удаление вершины и удаления ребра, построить матрицы инцидентности, а для графов, полученных в результате операций объединение, пересечение и соединение.
3. Определить, какими свойствами обладают графы G , G и графы, полученные из них: , G , G , G G . Результаты описать в виде таблицы:
| Пол-ный | Пус- той | Связ- ный | Дерево | Лес | Эйле-ров | Гамиль-тонов | Дву-дольный | Плос- кий | |
| G
| * | * | |||||||
| G
| * | * | |||||||
|
| * | ||||||||
| G
| * | ||||||||
| G
| * | ||||||||
| G G
| * |
отметив соответствующий результат знаком «+» или «−». Для клеточек, отмеченных символом «*», выводы обосновать.
Исходные данные:
| Группа 1 | Группа 2 | ||||
| G1 | G2 | G1 | G2 | ||
| (i, j) | (i, j) | (i, j) | (i, j) | ||
| (5; 7) | (4; 3) | (6; 6) | (4; 3) | ||
| (5; 6) | (4; 3) | (6; 5) | (4; 3) | ||
| (5; 5) | (4; 3) | (6; 4) | (4; 3) | ||
| (5; 4) | (4; 3) | (6; 3) | (4; 3) | ||
| (5; 2) | (4; 3) | (6; 7) | (4; 3) | ||
| (5; 1) | (4; 3) | (6; 5) | (4; 2) | ||
| (5; 7) | (4; 4) | (6; 4) | (4; 4) | ||
| (5; 6) | (4; 4) | (6; 3) | (4; 4) | ||
| (5; 5) | (4; 4) | (6; 6) | (4; 4) | ||
| (5; 4) | (4; 4) | (6; 5) | (4; 5) | ||
| (5; 2) | (4; 4) | (6; 4) | (4; 5) | ||
| (5; 1) | (4; 4) | (6; 3) | (4; 5) | ||
| (5; 7) | (4; 5) | (4; 2) | (4; 2) | ||
| (5; 6) | (4; 5) | (5; 6) | (4; 1) | ||
| (5; 5) | (4; 5) | (6; 7) | (4; 2) | ||
| (5; 4) | (4; 5) | (6; 7) | (5; 1) | ||
| (5; 2) | (4; 5) | (6; 7) | (5; 2) | ||
| (5; 1) | (4; 5) | (6; 5) | (5; 2) | ||
| (5; 7) | (4; 2) | (6; 6) | (5; 2) | ||
| (5; 6) | (4; 2) | (6; 4) | (5; 2) | ||
| (5; 5) | (4; 2) | (6; 3) | (5; 2) | ||
| (5; 4) | (4; 2) | (6; 7) | (5; 3) | ||
| (5; 2) | (4; 2) | (6; 2) | (5; 3) | ||
| (5; 1) | (4; 2) | (6; 4) | (5; 3) | ||
| (5; 0) | (5; 6) | (6; 1) | (5; 6) |
Первый столбец − параметры графа G , второй − графа G . В паре (i, j) первое число − число вершин, второе число − число ребер.