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

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

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

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

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

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

    • Какой-то граф
    • Заведомо неориентированный граф
    • Заведомо ориентированный граф
    • Граф с K несвязными областями
    • Сеть с одним истоком в первой и одним стоком в последней вершинах
    • Произвольную сеть
    • Ориентированный граф с циклами
    • <!> Нарисовать дерево/сеть/граф (с помощью PyGame, tkinter, черепахи или ещё чего-нибудь

  4. Нора суриката состоит из N комнат. Из некоторых комнат в другие ведут тоннели. План норы представлен словарём вида { Номер_комнаты: (Номер_комнаты0, Номер_комнаты1,…), …}, где номера комнат в кортеже означают существование тоннеля Номер_комнаты → Номер_комнаты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
    • В произвольном случае

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


CategoryClass CategoryVmsh

LecturesVMSH/Python/2013-02-08 (последним исправлял пользователь FrBrGeorge 2013-02-19 21:46:28)