Учебная страница курса биоинформатики,
год поступления 2011

Семестры Студенты Преподаватели

• 2023
• 2022
• 2021
• 2020
• 2019
• 2018
• 2017
• 2016

• ...

Графы

1. (0.5) Дан граф (см. пример графов 1). Напишите для этого графа представление в виде матрицы смежности, списка смежных вершин, в виде таблицы соседей.

2. (0.5) Для графа из примера 1 продемонстрируйте поиск пути от вершины d до вершины l с помощью поиска вглубь. Выбирать очередного соседа нужно в лексикографическом порядке.

3. (0.5)Для графа из примера 1 продемонстрируйте поиск кратчайшего пути от вершины k до вершины e.

4. (2) Напишите программу, которая получает на вход описание графа в виде списка смежности (файл, в котором на каждой строке через пробел написаны два имени вершины: вершина, из которой исходит ребро, и вершина, в которую входит ребро), получает с командной строки имена вершины отправления и вершины назначения, и выписывает какой-либо путь от вершины отправления в вершину назначения с помощью поиска вглубь.

5. (2) Напишите программу, которая получает на вход описание графа в виде списка смежности (см. выше), получает с командной строки имена вершины отправления и вершины назначения, и выписывает кратчайший путь от вершины отправления в вершину назначения с помощью поиска вширь.

6. (1.5) Для последовательности ATCAGATAGGAC продемонстрируйте алгоритм сборки генома: разбейте последовательность на перекрывающиеся участки длиной 3, преобразуйте граф и найдите в нем эйлеров цикл.

Примеры графов

1. Ориентированный граф:

   • digraph {
      a -> b -> c -> d;
      a -> d -> c -> b;
      f -> e -> b -> a;
      e -> g -> h -> c;
      c -> h -> g -> b;
      i -> j -> b -> e -> f -> j -> p -> c;
      k -> l -> a;
      i -> b;
      k -> b;
      j -> m -> n -> o -> c;
      m -> o;
     }