Презентация Алгоритмы на графах. Топологическая сортировка отсечением вершин

Смотреть слайды в полном размере
Презентация Алгоритмы на графах. Топологическая сортировка отсечением вершин


Вашему вниманию предлагается презентация «Алгоритмы на графах. Топологическая сортировка отсечением вершин», с которой можно предварительно ознакомиться, просмотреть текст и слайды к ней, а так же, в случае, если она вам подходит - скачать файл для редактирования или печати.

Презентация содержит 13 слайдов и доступна для скачивания в формате ppt. Размер скачиваемого файла: 667.50 KB

Просмотреть и скачать

Pic.1
Алгоритмы на графах. Топологическая сортировка отсечением вершин, слайд 1
Pic.2
Нахождение компонент связности В первой строке файла input. txt заданы целые n и m — соответственно
Нахождение компонент связности В первой строке файла input. txt заданы целые n и m — соответственно число вершин и число рёбер неориентированного графа (1 ≤ n ≤ 10 000, 0 ≤ m ≤ 50 000). В следующих m строках файла заданы пары номеров вершин, соединённых рёбрами. В файл output. txt вывести единственное число — количество компонент связности графа. Ограничение по времени — 1 сек. Ограничение по памяти — 16 Мб.
Pic.3
Домашнее задание Сколько различных путей есть в дереве с n вершинами? Какое максимальное количество
Домашнее задание Сколько различных путей есть в дереве с n вершинами? Какое максимальное количество циклов (длиной 3 и более) может быть в неориентированном графе с n вершинами? Какое максимальное количество циклов (длиной 3 и более) может быть в неориентированном графе с n вершинами и k компонентами связности? Написать программу, определяющую количество компонент связности, с использованием матрицы смежности. Написать программу, определяющую максимальный размер компоненты связности, с использованием списка смежности.
Pic.4
Топологическая сортировка Дан ориентированный ациклический граф.
Топологическая сортировка Дан ориентированный ациклический граф.
Pic.5
Топологическая сортировка Почему это возможно?
Топологическая сортировка Почему это возможно?
Pic.6
Топологическая сортировка Как быстро определить вершины, в которые не входит ни одно ребро?
Топологическая сортировка Как быстро определить вершины, в которые не входит ни одно ребро?
Pic.7
Топологическая сортировка массив order длины n, order[i] — присвоенный i-й вершине порядковый номер
Топологическая сортировка массив order длины n, order[i] — присвоенный i-й вершине порядковый номер при топологической сортировке; currorder — текущий присваиваемый номер.
Pic.8
Топологическая сортировка В первой строке файла input. txt заданы целые n и m — соответственно число
Топологическая сортировка В первой строке файла input. txt заданы целые n и m — соответственно число вершин и число рёбер ориентированного графа (1 ≤ n ≤ 10 000, 0 ≤ m ≤ 50 000). В следующих m строках файла заданы пары номеров вершин, соединённых рёбрами. В файл output. txt вывести номера, которые приобретут вершины после топологической сортировки. i-е число означает номер, приобретённый i-й вершиной. Ограничение по времени — 3 сек. Ограничение по памяти — 16 Мб.
Pic.9
Топологическая сортировка В первой строке файла input. txt заданы целые n и m — соответственно число
Топологическая сортировка В первой строке файла input. txt заданы целые n и m — соответственно число вершин и число рёбер ориентированного графа (1 ≤ n ≤ 10 000, 0 ≤ m ≤ 50 000). В следующих m строках файла заданы пары номеров вершин, соединённых рёбрами. В файл output. txt вывести упорядоченные топологически номера вершин. Ограничение по времени — 3 сек. Ограничение по памяти — 16 Мб.
Pic.10
Домашнее задание Предприятие «Авто-2010» выпускает двигатели известных во всём мире автомобилей. Дви
Домашнее задание Предприятие «Авто-2010» выпускает двигатели известных во всём мире автомобилей. Двигатель состоит ровно из n деталей, пронумерованных от 1 до n, при этом деталь с номером i изготавливается за pi секунд. Специфика предприятия «Авто-2010» заключается в том, что там одновременно может изготавливаться лишь одна деталь двигателя. Для производства некоторых деталей необходимо иметь предварительно изготовленный набор других деталей. Генеральный директор «Авто-2010» поставил перед предприятием амбициозную задачу — за наименьшее время изготовить деталь с номером 1, чтобы представить её на выставке. Требуется написать программу, которая по заданным зависимостям порядка производства между деталями найдёт наименьшее время, за которое можно произвести деталь с номером 1.
Pic.11
Домашнее задание Первая строка входного файла details. in содержит число n (1 ≤ n ≤ 10 000) — количе
Домашнее задание Первая строка входного файла details. in содержит число n (1 ≤ n ≤ 10 000) — количество деталей двигателя. Вторая строка содержит n натуральных чисел p1, p2, …, pn, определяющих время изготовления каждой детали в секундах. Время для изготовления каждой детали не превосходит 109 секунд. Каждая из последующих n строк входного файла описывает характеристики производства деталей. Здесь i-я строка содержит число деталей ki, которые требуются для производства детали с номером i, а также их номера. Сумма всех чисел ki не превосходит 200000. Известно, что не существует циклических зависимостей в производстве деталей. В первой строке выходного файла details. out должны содержаться два числа: минимальное время ( в секундах), необходимое для скорейшего производства детали с номером 1 и число k деталей, которые необходимы для этого производства. Во второй строке требуется вывести через пробел k чисел — номера деталей в том порядке, в котором их следует производить для скорейшего производтсва детали с номером 1. Ограничение по времени — 2 сек. Ограничение по памяти — 64 Мб.
Pic.12
Домашнее задание
Домашнее задание
Pic.13
Источники Курс «Базовые алгоритмы для школьников» (Станкевич А. С. , Абакумов К. В. , Мухачёва М. А.
Источники Курс «Базовые алгоритмы для школьников» (Станкевич А. С. , Абакумов К. В. , Мухачёва М. А. ) «Интернет-уинверситет информационных технологий»


Скачать презентацию

Если вам понравился сайт и размещенные на нем материалы, пожалуйста, не забывайте поделиться этой страничкой в социальных сетях и с друзьями! Спасибо!