-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy path1.14.html
66 lines (56 loc) · 6.71 KB
/
1.14.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
<!DOCTYPE html>
<html lang="ru">
<head>
<meta charset="UTF-8">
<title>Графы и их свойства</title>
<link rel="stylesheet" href="./css/index.css">
</head>
<body>
<div class="container">
<h1>Графы: определение, типы, пути и представление</h1>
<div class="navigation-buttons">
<a href="1.13.html" class="button">⬅ Назад</a>
<a href="1.15.html" class="button">Вперёд ➡</a>
</div>
<h2>Определение графа</h2>
<p><strong>Граф</strong> — это математическая структура, представляющая собой множество <em>вершин</em> и <em>рёбер</em>, которые соединяют пары вершин. Графы используются для моделирования различных объектов и связей между ними, таких как транспортные сети, социальные сети и схемы компьютерных сетей.</p>
<ul>
<li><strong>Вершины</strong> (или узлы) графа обозначаются как точки, представляющие объекты.</li>
<li><strong>Рёбра</strong> (или дуги) соединяют вершины и представляют связи между ними.</li>
</ul>
<h2>Типы графов</h2>
<p>Графы классифицируются по типу рёбер и наличию весов:</p>
<h3>Ориентированные и неориентированные графы</h3>
<ul>
<li><strong>Ориентированный граф (орграф):</strong> рёбра имеют направление. Каждое ребро соединяет пару вершин, но в определённом направлении. Обозначается как <code>(u → v)</code>, где <code>u</code> и <code>v</code> — вершины.</li>
<li><strong>Неориентированный граф:</strong> рёбра не имеют направления. Ребро обозначается как <code>{u, v}</code>, где <code>u</code> и <code>v</code> — соединённые вершины. Связь между вершинами симметрична.</li>
</ul>
<h3>Взвешенные графы</h3>
<p><strong>Взвешенный граф</strong> — это граф, в котором каждому ребру присвоен <em>вес</em>, представляющий собой численное значение. Взвешенные графы используются для моделирования сетей, где связь между вершинами имеет стоимость или расстояние (например, дороги между городами с указанием расстояний).</p>
<ul>
<li>В неориентированном взвешенном графе вес ассоциируется с обоими направлениями.</li>
<li>В ориентированном взвешенном графе вес указывается для конкретного направления рёбер.</li>
</ul>
<h2>Понятие пути в графе</h2>
<p><strong>Путь</strong> в графе — это последовательность рёбер, которая соединяет начальную и конечную вершины, проходя через промежуточные вершины, если они есть. Путь может быть:</p>
<ul>
<li><strong>Простым путём:</strong> путь, в котором ни одна вершина не повторяется (кроме, возможно, начальной и конечной в случае циклов).</li>
<li><strong>Циклом:</strong> путь, который начинается и заканчивается в одной и той же вершине, проходя через другие вершины.</li>
</ul>
<h3>Длина пути</h3>
<p><strong>Длина пути</strong> — это количество рёбер на пути между начальной и конечной вершинами. В случае взвешенного графа длина пути может быть определена как сумма весов рёбер, через которые проходит путь.</p>
<h2>Способы представления графов</h2>
<p>Существует несколько способов представления графов, каждый из которых имеет свои особенности и подходит для различных задач:</p>
<ul>
<li><strong>Матрица смежности:</strong> квадратная матрица, где элемент <code>matrix[i][j]</code> указывает наличие или вес ребра между вершинами <code>i</code> и <code>j</code>. Применяется для плотных графов.</li>
<li><strong>Список смежности:</strong> для каждой вершины хранится список её соседей (вершин, с которыми она соединена рёбрами). Подходит для разреженных графов, экономит память.</li>
<li><strong>Список рёбер:</strong> хранится список всех рёбер в виде пар вершин или троек (в случае взвешенных графов). Удобен для работы с графами, где требуется рассматривать отдельные рёбра.</li>
</ul>
<h2>Заключение</h2>
<p>Графы — это универсальная структура данных для представления объектов и их взаимосвязей. Ориентированные, неориентированные и взвешенные графы используются для моделирования различных систем, таких как транспортные сети и компьютерные сети. Понятие пути и длины пути помогает описывать связи между вершинами, а различные методы представления графов обеспечивают гибкость в выборе подходящего способа хранения и обработки данных.</p>
</div>
<div class="navigation-buttons">
<a href="1.13.html" class="button">⬅ Назад</a>
<a href="1.15.html" class="button">Вперёд ➡</a>
</div></body>
</html>