Документ взят из кэша поисковой машины. Адрес оригинального документа : http://uneex.mithril.cs.msu.su/LecturesVMSH/Python/2013-02-08
Дата изменения: Unknown
Дата индексирования: Sun Apr 10 05:00:53 2016
Кодировка: UTF-8
LecturesVMSH/Python/2013-02-08 - UNИX

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

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

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

  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 18:46:28)