Тест по предмету «Информатика» на тему «Определение графа»

1. Что называют графом в информатике?

2. Как записывают граф с помощью множеств и что обозначают \(V\) и \(E\) в записи \(G=(V,E)\)?

3. Дан граф \(G=(V,E)\), где \(V=\{A,B,C,D\}\), а \(E=\{\{A,B\},\{B,C\},\{C,D\}\}\). Сколько в нём вершин и рёбер?

4. В графе из задания 3 какие вершины являются соседними с вершиной \(B\)?

5. В неориентированном графе являются ли \(\{A,B\}\) и \(\{B,A\}\) одним и тем же ребром? Объясните ответ.

6. Дан ориентированный граф \(G=(V,E)\), где \(V=\{1,2,3\}\), а \(E=\{(1,2),(2,3),(3,1)\}\). Какое ребро выходит из вершины 2 и в какую вершину оно направлено?

7. Что называют степенью вершины в неориентированном графе?

8. В неориентированном простом графе рёбра заданы множеством \(E=\{\{A,B\},\{A,C\},\{B,C\},\{C,D\}\}\). Чему равна степень вершины \(C\)?

9. Что называют изолированной вершиной графа?

10. Сколько рёбер содержит полный неориентированный простой граф с пятью вершинами?

Ответы

1. Граф — это множество вершин и множество рёбер, соединяющих пары вершин.
2. \(G=(V,E)\); \(V\) — множество вершин, \(E\) — множество рёбер.
3. 4 вершины и 3 ребра.
4. Вершины \(A\) и \(C\).
5. Да, это одно и то же ребро, поскольку в неориентированном графе порядок вершин не имеет значения.
6. Ребро \((2,3)\), направленное из вершины 2 в вершину 3.
7. Число рёбер, инцидентных данной вершине.
9. Вершину, с которой не связано ни одно ребро; её степень равна 0.
10. 10 рёбер.