Скачать презентацию
Идет загрузка презентации. Пожалуйста, подождите
2
Граф – это совокупность непустого множества вершин и множества пар связей между ними Что такое граф?
3
Граф - обозначает «пишу». НО: График - это чертёж, на котором при помощи линий и других графических элементов показаны какие-либо числовые данные. Граф - это ( в случае теории графов) обозначает множество точек и линий между ними.
4
Если вершинам графа сопоставить буквы, числа или некую другую информацию, то такой граф является помеченным. Если ребрам графа поставлены в соответствие некие веса, такой граф называется взвешенным. Если все ребра графа являются ориентированными, то такой граф называется ориентированным или орграфом. Азы теории графов
5
В обыкновенном графе две вершины могут соединяться только одним ребром. Если они соединены более чем одним ребром, то такой граф называется мульти графом. Если вершина мультиграфа может соединяться сама с собой, то такой граф называется псевдо графом. Ребро, начало и конец которого находятся в одной вершине, называется петлей. Азы теории графов
6
Если между любыми двумя вершинами графа можно провести маршрут, то говорят, что граф является связным. Для связных графов имеет смысл определить расстояние между вершинами как минимальное количество ребер, образующих маршрут между ними. Несвязный граф – это граф, содержащий изолированную вершину
7
Ц ИКЛЫ это простые маршруты, проходящие через все вершины, начальная и конечная точка которых совпадают. Циклами можно представить маршруты городских автобусов или маршруты патрулей.
8
Дерево это простой граф, все вершины которого соединены так, что отсутствуют циклы Графы такого вида используются при решении комбинаторных задач, когда надо осуществить перебор всех возможных вариантов. Задача. В столовой на горячее можно заказать щуку, грибы и баранину, на гарнир – картофель и рис, а из напитков – чай и кофе. Сколько различных вариантов обедов можно составить из указанных блюд?
9
Основоположником теории графов считают Леонарда Эйлера. В 1736 году он остановился в Кёнигсберге. Город был разделен рекой на четыре части, которые были соединены семью мостами. Через два рукава реки перекинуто семь мостов. Задача состояла в том, чтобы определить, можно ли обойти все мосты, пройдя по каждому ровно один раз? Леонард Эйлер
10
В 1847 году Густав Кирхгоф использовал схемы, подобные графам, при изучении электрических цепей В 1857 году Артур Кэли изучал число изомеров органического соединения с помощью графов, в которых точки соединялись между собой одной или четырьмя линиями - по числу химических связей Где и как используют графы? Густав Кирхгоф Артур Кэли
11
Психолог Курт Левин ввел в психологию схемы, на которых люди обозначались точками, а личные отношения между ними линиями. Физики Уленбек, Ли и Янг использовали схемы из точек и линий для изображения структур молекул и взаимодействия между ними. Курт Левин Уленбек Ли и Янг
12
При работе над архитектурными проектами интерес представляет анализ графа доступности пространств. Функциональное зонирование квартиры
13
Родословную человека или семьи можно представить в четкой и упорядоченной форме с помощью графа, в вершинах которого размещаются фотографии, имена и годы жизни родственников, а ребра графа указывают на родственные отношения.
14
Наручные часы это граф с 12 вершинами. Карты и автомобильные маршруты, представленные в интернете, - пример использования графов. Ребрами в них являются улицы и автодороги, вершинами - населенные пункты.
15
Большинство географических карт можно интерпретировать как графы, вершинами которых являются точки, где сходятся три линии и более, а ребрами границы стран и территорий.
16
В виде орграфов можно представить энергосети, транспортные потоки, телефонные сети, схемы промышленного производства, порядок действий при ремонте и многое другое.
17
Классические примеры древовидных городов - это Большой Лондон Лесли Патрика Аберкромби и Джона Форшоу, план Токио авторства Кэндзо Тангэ, план города Бразилиа архитектора Лусио Косты, план Чандигарха, созданный Ле Корбюзье
Еще похожие презентации в нашем архиве:
