Тема 27. Основы теории графов

Основные понятия

№3.1.1. Для графов, приведенных на рис.1., выполните следующие задания:

1) определите степени и полустепени вершин;

2) укажите содержащиеся в них:

а) контуры (циклы),

б) петли,

в) узлы,

г) висячие вершины;

3) определите, какие из графов являются:

а) ориентированными,

б) однородными,

в) полными,

г) мультиграфами.

1. х₂ х₃ 2. х₂ х₃

х₁ х₄

х₁ х₄

х₃ х₃

3. х₂ 4.

х₄ х₂ х₄

х₁ х₅

х₁ х₅

№3.1.2. По заданным полустепеням вершин постройте, если это возможно, ориентированный граф:

1) Р₊(х_i)=1, P_(x_i)=1, i=1,…,4;

2) P₊(x₁)=P₊(x₂)=P_(x₂)=P_(x₃)=1,

P₊(x₃)=P_(x₁)=2;

3) P₊(x_i)=i, P_(x_i)=6-i, i=1,…,5.

№3.1.3. По данной матрице смежности постройте ориентированный граф и, если это возможно, неориентированный граф. Определите степени и полустепени вершин.

1) 0 1 0 2) 0 1 1 3) 0 1 1 1 4) 0 1 1 1

1 0 1 1 0 0 0 0 0 0 1 0 0 0

1 0 0 1 0 0 0 1 0 1 0 1 0 1

0 1 1 0 1 0 0 1

Литература:[4,11]

Учебно-методическая литература:[6]

Не нашли, что искали? Воспользуйтесь поиском: