Презентация на тему Факультативное занятие по математике в 6 классе Связный граф. Компонента связности

Какой граф называется нулевым?
3. Какой граф называется неполным?
4. Как

проверить, является ли граф полным?
5. Что называется степенью вершины графа?
6. Какая вершина графа называется нечётной?
7. Какая вершина графа называется чётной?

гор и рек. В ней есть шесть городов: А,

Б, В, Г, Д и Е. Известно, что из А проложены дороги в Б и Г, из Б — в А, Г и Д, из В — в Г и Е, из Г — в В и Д, из Д — в Б и Г, из Е — только в В. Все остальные дороги непроходимы.
а)Нарисуйте карту страны Фарг.
б)Нарисуйте карту так, чтобы дороги не пересекались.
в) Может ли житель города Е попасть в город Б?
г)Может ли житель города А попасть в город Д, если ему нельзя проходить через Г?
д)Сможет ли он при тех же условиях попасть в город Е?

по рёбрам добраться до любой другой (и несвязным иначе).

не менее (n-1) рёбер.  Если граф имеет не менее (n∙n -

3n + 4)/2 рёбер, то он гарантированно связный.  Если граф связный, у него обязательно есть вершины степени не менее 2, то есть вершины, каждая из которых имеет не менее двух смежных вершин. 

это дерево), то удаление любого ребра приведёт к потере

связности. 

- множество вершин такое, что из любой вершину этого

множества есть путь в любую другую вершину этого множества, но ни из какой вершины этого множества нельзя попасть в некоторую вершину вне этого множества. Очевидно, что сумма количеств вершин компонент связности равна количеству вершин графа.