Список смежности
Список смежности — это способ представить граф: для каждой вершины записывают все вершины, соединённые с ней ребром. По такой записи можно восстановить связи графа, найти соседей вершины и определить её степень.
Как читать список
Обычно запись имеет вид: вершина: её соседи. Например, строка 2: 1, 4, 5 означает, что вершина 2 соединена с вершинами 1, 4 и 5. Значит, из вершины 2 можно перейти непосредственно в 1, 4 или 5, если граф неориентированный.
Здесь \(d(v)\) — степень вершины \(v\), а \(N(v)\) — список её соседей. Поэтому степень равна количеству элементов в списке. Для неориентированного графа каждое ребро обычно появляется в списках обеих его вершин: если указано 2: 1, то должно быть и 1: 2.
Дан список: 1: 2, 3; 2: 1, 4; 3: 1; 4: 2. У вершины 2 соседи 1 и 4, поэтому её степень равна 2. Ребро между 1 и 3 записано дважды: в строках вершин 1 и 3.
В списке смежности записано 5: 2, 6, 7. Сколько рёбер выходит из вершины 5 в неориентированном графе?
В матрице смежности связи задаются таблицей из нулей и единиц, а в списке смежности перечисляются только фактические соседи. В ориентированном графе направление важно: список исходящих соседей вершины может не совпадать со списком входящих.
Что проверять в задачах
- Чтобы найти соседей вершины, прочитайте строку с её номером.
- Чтобы найти степень, посчитайте элементы в её списке.
- В неориентированном графе проверяйте симметричность записи: соседство должно быть указано в обеих строках.
Главное
- Список смежности перечисляет соседей каждой вершины.
- Количество соседей равно степени вершины.
- В неориентированном графе каждое ребро указывают в списках обеих его вершин.