Графы Основные понятия

  • Просмотров 1139
  • Скачиваний 67
  • Размер файла 85
    Кб

Министерство образования и науки Российской Федерации Курский государственный технический университет Кафедра ПО ВТ и АС Лабораторная работа № 1 Графы. Основные понятия Выполнил: студент гр. ПО 62 Шиляков И.А. Проверил: доцентТомакова Р.А. Курск 2007 Задание: По заданным матрицам смежности вершин восстановить графы. Построить для каждого графа матрицу смежности ребер, инцидентности, достижимости, контрдостижимости. Найти и

построить объединение, пересечение, кольцевую сумму заданных графов. Найти композицию графов . Для каждого графа найти и построить остовный подграф, произвольный подграф, порожденный подграф. Определить локальные степени вершин графа, проверить существует ли в данном графе эйлерова цепь, эйлеров цикл. Определить хроматические и цикломатические числа данных графов. Найти все базы графа. Определить в каждом графе сильные

компоненты связности, построить конденсацию графа. Выполнение: По заданным матрицам смежности вершин восстановить графы. x1 x2 x3 x4 x5 x6 x7 x1 0 1 0 0 0 0 1 x2 0 0 1 0 0 1 0 x3 0 1 0 1 0 0 0 x4 1 0 0 0 1 0 0 x5 1 0 0 0 0 0 1 x6 0 0 1 1 0 0 0 x7 0 0 0 0 1 1 0 A1 X2 G1(X1,A1) x1 x2 x3 x4 x5 x6 x7 x1 0 1 1 0 0 0 0 x2 0 0 0 1 1 0 0 x3 0 1 0 0 0 0 1 x4 1 0 0 0 1 0 0 x5 0 0 0 0 0 1 1 x6 1 0 0 1 0 0 0 x7 0 0 1 0 0 1 0 A2 X2 G2(X2,A2) Построить для каждого графа матрицу смежности ребер, инцидентности, достижимости, контрдостижимости. а1 а2 а3 а4 а5 а6 а7 а8 а9 а10 а11 а12 а13 а14 а1

0 1 1 1 1 0 1 0 1 0 0 0 0 0 а2 1 0 0 0 0 0 1 0 1 1 0 0 1 1 а3 1 0 0 1 1 1 0 0 0 0 1 0 0 0 а4 1 0 1 0 1 0 0 0 0 0 1 1 0 1 а5 1 0 1 1 0 1 0 0 0 0 1 0 0 0 а6 0 0 1 0 1 0 1 1 0 0 1 1 0 0 а7 1 1 0 0 0 1 0 1 1 0 0 1 0 0 а8 0 0 0 0 0 1 1 0 1 1 0 1 1 0 а9 1 1 0 0 0 0 1 1 0 1 0 0 1 0 а10 0 1 0 0 0 0 0 1 1 0 0 0 1 1 а11 0 0 1 1 1 1 0 0 0 0 0 1 0 1 а12 0 0 0 1 0 1 1 1 0 0 1 0 0 1 а13 0 1 0 0 0 0 0 1 1 1 0 0 0 1 а14 0 1 0 1 0 0 0 0 0 1 1 1 1 0 B1 а1 а2 а3 а4 а5 а6 а7 а8 а9 а10 а11 а12 а13 а14 а1 0 1 0 1 1 1 1 0 1 0 0 0 0 0 а2 1 0 1 1 1 1 0 1 0 0 0 0 0 0 а3 0 1 0 1 0 0 1 1 0 0 0 1 1 0 а4 1 1 1 0 0 0 1 1 1 0 0 0 0 0 а5 1 1 0 0 0 1 0 0 0 1 1 0 0 0 а6 1 1 0 0 1 0 0 0 0 1 1 0 0 0 а7 1 0 1 1 0 0 0 0 1 0 0 1 1 0 а8 0 1 1 1 0 0 0 0 0 0 1 0 1 1 а9 1 0 0 1 0 0 1 0 0

1 0 1 0 1 а10 0 0 0 0 1 1 0 0 1 0 1 1 0 1 а11 0 0 0 0 1 1 0 1 0 1 0 0 1 1 а12 0 0 1 0 0 0 1 0 1 1 0 0 1 1 а13 0 0 1 0 0 0 1 1 0 0 1 1 0 1 а14 0 0 0 0 0 0 0 1 1 1 1 1 1 0 B2 а1 а2 а3 а4 а5 а6 а7 а8 а9 а10 а11 а12 а13 а14 x1 1 1 0 0 0 0 -1 0 -1 0 0 0 0 0 x2 -1 0 1 1 -1 0 0 0 0 0 0 0 0 0 x3 0 0 -1 0 1 1 0 0 0 0 -1 0 0 0 x4 0 0 0 0 0 -1 1 1 0 0 0 -1 0 0 x5 0 0 0 0 0 0 0 -1 1 1 0 0 -1 0 x6 0 0 0 -1 0 0 0 0 0 0 1 1 0 -1 x7 0 -1 0 0 0 0 0 0 0 -1 0 0 1 1 S1 а1 а2 а3 а4 а5 а6 а7 а8 а9 а10 а11 а12 а13 а14 x1 1 0 0 1 0 0 -1 0 -1 0 0 0 0 0 x2 0 -1 1 -1 0 0 0 1 0 0 0 0 0 0 x3 -1 1 0 0 -1 1 0 0 0 0 0 0 0 0 x4 0 0 -1 0 0 0 1 0 0 0 0 -1 1 0 x5 0 0 0 0 0 0 0 -1 0 0 1 0 -1 1 x6 0 0 0 0 0 0 0 0 1 -1 0 1 0 -1 x7 0 0 0 0 1 -1 0 0 0 1 -1 0 0 0 S2 x1 x2 x3 x4 x5 x6 x7