Графы, их представление и использование

Какое-нибудь описание.

• Деревья и их (не)актуальность в Python
• Связность графа
• Ориентированные и неориентировнные графы
• Циклы в графах
• Представление графов в Python
• Обход графа вглубь и вширь

Домашнее задание

1. Почитать про графы в Википедии; про Поиск в глубину и Поиск в ширину на сайте MCCME

2. Сгенерировать случайное дерево и вывести его красиво на экран

   • 2013-02-08.printtree.py

   • Сеть? (возможно, понадобится работа с графикой?)

3. Сгенерировать и представить в виде списка рёбер: 2013-02-08.graph-gen.py

   • Какой-то граф
   • Заведомо неориентированный граф
   • Заведомо ориентированный граф
   • Граф с K несвязными областями
   • Сеть с одним истоком в первой и одним стоком в последней вершинах
   • Произвольную сеть
   • Ориентированный граф с циклами

   • Нарисовать дерево/сеть/граф (с помощью PyGame, tkinter, черепахи или ещё чего-нибудь

     • 2013-02-08.drawgraph-dumb.py

4. Нора суриката состоит из N комнат. Из некоторых комнат в другие ведут тоннели. План норы представлен словарём вида { Номер_комнаты: (Номер_комнаты₀, Номер_комнаты₁,…), …}, где номера комнат в кортеже означают существование тоннеля Номер_комнаты → Номер_комнаты_k

   • Определить, корректно ли представлен план (является ли он неориентирванным графом)
   • Можно ли попасть из любой комнаты в любую (определить число несвязных компонент)
   • Определить кратчайший путь из комнаты 0 в комнату N-1

     Пример входных данных:

        1    { 0: (2,7),
        2      1: (3,4,6),
        3      2: (5,0,7),
        4      3: (6,1),
        5      4, (3,6),
        6      5: (2,),
        7      6: (1,4),
        8      7: (0,2), }
     

     Это корректный двухсвязный неориентированный граф
5. Ввести ориентированный граф, сгененрированный генератором #2, и проверить, является ли он сетью
   • В случае одного истока в 0 и одного стока в N-1
   • В произвольном случае

Условные обозначения

• — тема по Linux

• ­— тема повышенной сложности

• — теоретическое задание

• — тема для самостоятельного изучения

CategoryClass CategoryVmsh