Графы и их применение

Упражнение 1:

Номер 1

Что такое сеть?

Ответ:

(1) cеть N - это орграф, каждой дуге α которого приписано неотрицательное действительное число ψ(α), называемое ее пропускной способностью

(2) cеть представляет собой пару D(ψ) где D - орграф, а ψ - функция, отображающая множество дуг орграфа D в множество неотрицательных действительных чисел

(3) cеть представляет собой пару D(ψ) где D - орграф, а ψ - функция, отображающая множество дуг орграфа D в множество отрицательных действительных чисел

(4) допустим, что множество вершин графа можно разбить на два непересекающихся подмножества V₁ и V₂ так, что каждое ребро в G соединяет какую-нибудь вершину из V₁ с какой-либо вершиной из V₂, тогда граф G называется сетью

Номер 2

Что называется полустепенью исхода  вершины x?

Ответ:

(1) полустепень исхода вершины x определяется как разность пропускных способностей дуг вида (x,z)

(2) полустепенью исхода x называется число дуг из D вида (w,x)

(3) если x вершина орграфа D, то полустепенью исхода x называют число дуг орграфа D, имеющих вид (x,w)

(4) полустепень исхода вершины x определяется как сумма пропускных способностей дуг вида (x,z)

Номер 3

Что называется полустепенью захода вершины x?

Ответ:

(1) если в графе все вершины имеют счетную степень, то эта степень называется полустепенью захода

(2) если x вершина орграфа D, то полустепенью захода x называют число дуг орграфа D, имеющих вид (x,w)

(3) полустепень захода вершины x определяется как сумма пропускных способностей дуг вида (x,z)

(4) полустепенью захода x называется число дуг из D вида (w,x)

Упражнение 2:

Номер 1

Что называется разрезом в сети?

Ответ:

(1) такое множество A дуг орграфа D, которое обладает тем свойством, что любая простая орцепь из v в w проходит через дугу, принадлежащую A

(2) разрезом в сети является не что иное, как vw - разделяющее множество соответствующего орграфа D

(3) разрезом в сети является не что иное, как функция, составляющая каждой дуге α из D неотрицательное действительное число ϕ(α) (называемое потоком через α) таким образом , что ϕ(α)≤ψ(α) для любой дуги α

(4) разрезом в сети является N=(D,ψ)

Номер 2

Что называется потоком через сеть N?

Ответ:

(1) для данной сети N=(D,ψ) поток определяется через N как функцию ϕ, составляющую каждой дуге α из D неотрицательное действительное число ϕ(α) (называемое потоком через α) таким образом , что ϕ(α)≤ψ(α) для любой дуги α; по отношению к сети (D,ϕ) полустепень исхода и полустепень захода любой вершины (отличной от v и w) равны между собой

(2) для данной сети N=(D,ψ) поток определяется через N как функцию ϕ, составляющую каждой дуге α из D неотрицательное действительное число ϕ(α) (называемое потоком через α) таким образом , что ϕ(α)≤ψ(α) для любой дуги α; по отношению к сети (D,ϕ) полустепень исхода и полустепень захода любой вершины (отличной от v и w) неравны между собой

(3) для данной сети N=(D,ψ) поток определяется через N как функцию ϕ, составляющую каждой дуге α из D неотрицательное действительное число ϕ(α) (называемое потоком через α) таким образом , что ϕ(α)≤ψ(α) для любой дуги α; по отношению к сети (D,ϕ) полустепень исхода больше полустепени захода

(4) для данной сети N=(D,ψ) поток определяется через N как функция ϕ, составляющая каждой дуге α из D неотрицательное действительное число ϕ(α) (называемое потоком через α) таким образом , что ϕ(α)≤ψ(α) для любой дуги α; по отношению к сети (D,ϕ) полустепень исхода меньше полустепени захода любой вершины (отличной от v и w)

Номер 3

Какая дуга в сети называется насыщенной?

Ответ:

(1) дуга α, для которой ϕ(α)=ψ(α), в сети N=(D,ψ)

(2) дуга α, для которой ϕ(α)≠ψ(α), в сети N=(D,ψ)

(3) дуга α, для которой ϕ(α)≤ψ(α), в сети N=(D,ψ)

(4) дуга α, для которой ϕ(α)≥ψ(α), в сети N=(D,ψ)

Упражнение 3:

Номер 1

Что называют величиной потока?

Ответ:

(1) cумма потоков через дуги, инцидентные v, равна сумме потоков через дуги, инцидентные w

(2) cумма потоков через дуги, инцидентные v, равна сумме потоков через дуги, инцидентные w, увеличенная на число вершин сети

(3) cумма потоков через дуги, инцидентные v, равна сумме потоков через дуги, инцидентные w, уменьшенная на число вершин сети

(4) cумма потоков через дуги, инцидентные v, равна сумме потоков через дуги, инцидентные w, поделенная на число вершин

Номер 2

Что называется пропускной способностью разреза?

Ответ:

(1) сумма пропускных способностей, принадлежащих ему дуг

(2) сумма пропускных способностей, не принадлежащих ему дуг

(3) сумма степеней вершин данной сети

(4) сумма всех ребер, принадлежащих этому разрезу

Номер 3

Может ли в сети  величина любого максимального потока быть равна пропускной способности любого минимального разреза?

Ответ:

(1) во всякой сети величина любого максимального потока равна пропускной способности любого минимального разреза

(2) во всякой сети величина любого максимального потока меньше пропускной способности любого минимального разреза

(3) во всякой сети величина любого максимального потока больше пропускной способности любого минимального разреза

(4) данные величины несравнимы

Графы и их применение - тест 17