Matematické Fórum

Ahoj, potřebuji poradit:
Uvažujme graf d-dimenzionální hyperkrychle (d >= 2). To je graf, jehož vrcholy jsou posloupnosti nul a jedniček délky d a dva vrcholy jsou spojeny, právě když se jejich posloupnosti liší v jediné souřadnici. Každé hraně přidělíme jednotkovou kapacitu.

a) Najděte maximální tok ze z = (0, 0, 0, . . . , 0) do s = (1, 1, 1, . . . , 1).

b) Najděte maximální tok ze zdroje z = (0, 0, 0, . . . , 0) do stoku s = (1, 1, 1, . . . , 1), takový, aby každou hranou protékal nenulový tok.

c) Najděte maximální tok ze z = (1, 1, . . . , 1, 1, 0) do s = (1, 1, 1, . . . , 1).

Asi zde bude nějaký háček, protože ať hrany probírám, jak chci, pořád mi u a), b) i c) vychází stejný výsledek d. Protože ze zdroje vychází d hran s kapacitou 1 (tok velikosti d) a do stoku vchází také d hran, přičemž graf se nikde nezužuje natolik, aby zmenšil tento tok (od zdroje se rozvětvuje a srůstá až těsně u stoku; každý vrchol je d-tého stupně).