2 added
2 removed
Original
2026-01-01
Modified
2026-02-26
1
<p>Теория графов применяется, чтобы решать задачи разного типа. Например, нам нужно найти путь из одного города в другой, съездить туда и обратно или узнать стоимость перевозки. Чтобы правильно решить поставленную задачу, применяют графы разных типов.</p>
1
<p>Теория графов применяется, чтобы решать задачи разного типа. Например, нам нужно найти путь из одного города в другой, съездить туда и обратно или узнать стоимость перевозки. Чтобы правильно решить поставленную задачу, применяют графы разных типов.</p>
2
<p>В этом уроке разберем, какие типы графов существуют и для каких задач они подходят.</p>
2
<p>В этом уроке разберем, какие типы графов существуют и для каких задач они подходят.</p>
3
<p>Когда мы работаем с задачей, нужно понимать, с каким типом графов работаем. Выделим три основных типа:</p>
3
<p>Когда мы работаем с задачей, нужно понимать, с каким типом графов работаем. Выделим три основных типа:</p>
4
<ul><li>Неориентированные</li>
4
<ul><li>Неориентированные</li>
5
<li>Направленные</li>
5
<li>Направленные</li>
6
<li>Взвешенные</li>
6
<li>Взвешенные</li>
7
</ul><p>Разберем каждый тип подробнее.</p>
7
</ul><p>Разберем каждый тип подробнее.</p>
8
<h2>Неориентированные графы</h2>
8
<h2>Неориентированные графы</h2>
9
<p>Неориентированными называют графы, если между их узлами нет заданных направлений. Поэтому ребро из узла A в B будет идентично ребру из B в A:</p>
9
<p>Неориентированными называют графы, если между их узлами нет заданных направлений. Поэтому ребро из узла A в B будет идентично ребру из B в A:</p>
10
<p>В приведенном выше графе каждый узел может представлять различные города, а ребра показывают двунаправленные дороги.</p>
10
<p>В приведенном выше графе каждый узел может представлять различные города, а ребра показывают двунаправленные дороги.</p>
11
<h2>Направленные графы</h2>
11
<h2>Направленные графы</h2>
12
-
<p>У<strong>направленных графов</strong>или<strong>диграфов</strong>есть ориентация или направление между узлами. Получается, если есть ребро из узла A в B, вы можете двигаться только из A в B, так как другое направление не указано:</p>
12
+
<p>У<strong>направленных графов</strong>или<strong>диграфов</strong>есть ориентация или направление между узлами. Получается, если есть ребро из узла A в узел B, вы можете двигаться только из A в B, так как другое направление не указано:</p>
13
<p>Снова представим, что узлы - это города. У нас есть направление из города 1 в город 2. Получается, вы можете проехать по этому пути, но не обратно в город 1, так как нет направления обратно в город 1 из города 2. При этом граф может быть двунаправленным. Например, города 3 и 4 имеют направления в обе стороны.</p>
13
<p>Снова представим, что узлы - это города. У нас есть направление из города 1 в город 2. Получается, вы можете проехать по этому пути, но не обратно в город 1, так как нет направления обратно в город 1 из города 2. При этом граф может быть двунаправленным. Например, города 3 и 4 имеют направления в обе стороны.</p>
14
<h2>Взвешенные графы</h2>
14
<h2>Взвешенные графы</h2>
15
-
<p>У<strong>взвешенных графов</strong>есть ребра, которым присвоены<strong>весы</strong>- некоторые числа. Например, они могут отражать стоимость перевозки груза, расстояние, которое нужно преодолеть. Это данные, с которыми нам нужно проводить различные действия. Пример взвешенных графов:</p>
15
+
<p>У<strong>взвешенных графов</strong>есть ребра, которым присвоены<strong>веса</strong>- некоторые числа. Например, они могут отражать стоимость перевозки груза, расстояние, которое нужно преодолеть. Это данные, с которыми нам нужно проводить различные действия. Пример взвешенных графов:</p>
16
<p>Взвешенные графы бывают и направленными, и неориентированными. В примере выше неориентированный взвешенный граф. Стоимость или расстояние от зеленого узла до оранжевого и наоборот равна трем. Допустим, вы хотите проехать между двумя городами - зеленым и оранжевым. Значит, вам предстоит проехать три мили.</p>
16
<p>Взвешенные графы бывают и направленными, и неориентированными. В примере выше неориентированный взвешенный граф. Стоимость или расстояние от зеленого узла до оранжевого и наоборот равна трем. Допустим, вы хотите проехать между двумя городами - зеленым и оранжевым. Значит, вам предстоит проехать три мили.</p>
17
<p>Эти метрики определяются самостоятельно и могут быть изменены в зависимости от ситуации. Предположим, вам нужно попасть в розовый город из зеленого. Если посмотреть на граф города, мы не найдем прямых дорог или ребер между этими двумя городами. Поэтому мы можем поехать через другой город.</p>
17
<p>Эти метрики определяются самостоятельно и могут быть изменены в зависимости от ситуации. Предположим, вам нужно попасть в розовый город из зеленого. Если посмотреть на граф города, мы не найдем прямых дорог или ребер между этими двумя городами. Поэтому мы можем поехать через другой город.</p>
18
<p>Наиболее перспективными будут маршруты из зеленого в розовый через оранжевый и синий. Если весами являются затраты между городами, то нам придется потратить 11 долларов на поездку через синий город, чтобы добраться до розового. Если мы воспользуемся другим маршрутом через оранжевый город, то нам придется заплатить за поездку всего десять долларов.</p>
18
<p>Наиболее перспективными будут маршруты из зеленого в розовый через оранжевый и синий. Если весами являются затраты между городами, то нам придется потратить 11 долларов на поездку через синий город, чтобы добраться до розового. Если мы воспользуемся другим маршрутом через оранжевый город, то нам придется заплатить за поездку всего десять долларов.</p>
19
<p>Каждое ребро может иметь несколько весовых коэффициентов - расстояние, время в пути или денежные затраты. Такие взвешенные графы обычно используются для программирования GPS и поисковых систем планирования путешествий, которые сравнивают время и стоимость перелета.</p>
19
<p>Каждое ребро может иметь несколько весовых коэффициентов - расстояние, время в пути или денежные затраты. Такие взвешенные графы обычно используются для программирования GPS и поисковых систем планирования путешествий, которые сравнивают время и стоимость перелета.</p>
20
<p>Типы графов можно определять по признакам, которые мы разобрали в этом уроке. Например, если вы увидите направление от одного узла к другому - это диграфы. Если у них еще есть ребра с числами - это направленные взвешенные графы. Когда вы научитесь определять тип графов, то сможете правильно решать задачи.</p>
20
<p>Типы графов можно определять по признакам, которые мы разобрали в этом уроке. Например, если вы увидите направление от одного узла к другому - это диграфы. Если у них еще есть ребра с числами - это направленные взвешенные графы. Когда вы научитесь определять тип графов, то сможете правильно решать задачи.</p>
21
<h2>Выводы</h2>
21
<h2>Выводы</h2>
22
<p>В этом уроке мы познакомились с тремя основными типами графов:</p>
22
<p>В этом уроке мы познакомились с тремя основными типами графов:</p>
23
<ul><li>Неориентированные графы без заданных направлений</li>
23
<ul><li>Неориентированные графы без заданных направлений</li>
24
<li>Направленные с указанными направлениями</li>
24
<li>Направленные с указанными направлениями</li>
25
<li>Взвешенные с весами - числами на ребрах</li>
25
<li>Взвешенные с весами - числами на ребрах</li>
26
</ul><p>Эти знания помогут вам верно выбирать тип графа под реальную задачу и наглядно показывать свои вычисления.</p>
26
</ul><p>Эти знания помогут вам верно выбирать тип графа под реальную задачу и наглядно показывать свои вычисления.</p>