Замечание.

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

Диаметром связного графа называется число .

Центром связного графа называется вершина такая, что

, величина называется радиусом и обозначается .

 

34. Найти количество центров, радиус и диаметр каждого из деревьев, изображенных на рис. 43.

 

35. Изобразить все попарно неизоморфные ориентированные псевдографы, содержащие:

1) 2 вершины и 2 дуги;

2) 2 вершины и 3 дуги;

3) 3 вершины и 2 дуги.

Сколько среди них сильно связных, односторонне связных и слабо связных?

 

36. Построить все попарно неизоморфные направленные графы, имеющие:

1) 3 вершины и хотя бы одну дугу;

2) 4 вершины и 4 дуги;

3) 5 вершин и 3 дуги.

Сколько среди них сильно связных, односторонне связных и слабо связных?

 

38. Построить все попарно неизоморфные турниры с:

1) 3 вершинами;

2) 4 вершинами.

Сколько среди них сильно связных, односторонне связных и слабо связных?