Question

В графе есть вершины A,B,C,D и есть дуги AB,BC,BD,CA,CB,DA,DC.Какую дугу можно убрать, не разомкнув ни одного цикла?
​

Answer 1

Чтобы понять, какую дугу можно убрать, не разомкнув ни одного цикла, нам нужно посмотреть на граф и найти все циклы.
Построим все возможные циклы, используя заданные дуги.

1) Для начала, нарисуем данный граф:

A ---- B
| \ |
| \ |
| \ |
D ---- C

2) Теперь найдем все возможные циклы. Циклом называется последовательность вершин, которые начинаются и заканчиваются в одной и той же вершине, и между вершинами есть дуги.

В данном графе у нас есть три возможных цикла:
- A -> B -> C -> A
- A -> B -> D -> A
- A -> D -> C -> A

3) Теперь посмотрим на каждую дугу в графе и попробуем представить, что убираем эту дугу и смотрим, разомкнется ли какой-либо цикл.

- Если мы уберем дугу AB, то мы разомкнем цикл A -> B -> C -> A, поэтому эту дугу нельзя убрать.
- Если мы уберем дугу BC, то мы разомкнем цикл A -> B -> C -> A, поэтому эту дугу нельзя убрать.
- Если мы уберем дугу BD, то мы разомкнем цикл A -> B -> D -> A, но остальные циклы A -> B -> C -> A и A -> D -> C -> A останутся замкнутыми, поэтому эту дугу можно убрать и не разорвать все циклы.
- Если мы уберем дугу CA, то мы разомкнем цикл A -> C -> B -> A, но остальные циклы A -> B -> C -> A и A -> D -> C -> A останутся замкнутыми, поэтому эту дугу можно убрать и не разорвать все циклы.
- Если мы уберем дугу CB, то мы разомкнем цикл A -> C -> B -> A, но остальные циклы A -> B -> C -> A и A -> D -> C -> A останутся замкнутыми, поэтому эту дугу можно убрать и не разорвать все циклы.
- Если мы уберем дугу DA, то мы разомкнем цикл A -> D -> C -> A, поэтому эту дугу нельзя убрать.
- Если мы уберем дугу DC, то мы разомкнем цикл A -> D -> C -> A, поэтому эту дугу нельзя убрать.

Таким образом, можно убрать дугу BD, CA и CB не разомкнув ни одного цикла.