Mam 5 wierzchołkowy graf pełny, oraz nieposortowany zbiór wag krawędzi (waga krawędzi to suma wag wierzchołków do których należy krawędź). Szukam wag wierzchołków.

Z oczywistych sum wag wierzchołków wynika, że najmniejsza liczba z podanego zbioru to suma wag wierzchołków z najmniejszymi wagami. a największa liczba to suma wag wierzchołków z największymi wagami, ale nie potrafię przypisać konkretnych wag to wierzchołków.

Układ 5-ciu równań z 5-oma niewiadomymi?

dzieki za odpowiedz ale ale to mi niewiele mowi, niestety

masz wierzchołki: A, B, C, D, E
dane masz wagi krawędzi, czyli: AB, ..., DE - 10 krawędzi

waga krawędzi to suma wag wierzchołków do których należy krawędź, czyli:
waga(AB) = waga(A) + waga(B)
pomijając waga(), mamy
AB = A + B
AC = A + C
AD = A + D
AE = A + E
BC = B + C
BD = B + D
BE = B + E
CD = C + D
CE = C + E
DE = D + E

A rozwiązanie 10 równań z 5 niewiadomymi to już łatwizna - poziom gimnazjum. Czy coś źle zrozumiałem?

Łatwiej chyba wygrać w totolotka niż trafić na niejednorodny układ 10 równań z 5 niewiadomymi, który ma rozwiązanie.

ale ja nie wiem która krawędź należy do których wierzchołków, więc musiałbym zrobić n^2 porównań żeby taki układ rozwiązać, więc chyba nie o to chodzi.

Masz ograniczenia czasowe? Jeśli nie, to możesz spróbować brute force. Krawędzi jest 10, zatem do rozwiązania jest tylko 10! układów równań.

a co powiecie na to:

K5 składa się z trójkątów, jeśli wybierzemy 3 krawędzie, to co najmniej dwie z nich są bokami jakiegoś trójkąta, więc:

Uwagi:

• wszystkie krawędzie znajdują się w zbiorze E
• ilekroć wybieramy XY, które nie było wcześniej wspominane, należy rozumieć, że wybieramy dowolną krawędź i zakładamy, że jest to krawędź XY
• algorytm ma charakter algorytmu z nawrotami i mimo, że nawroty nie są zbyt wyraźnie zaznaczone, tak właśnie należy rozumieć algorytm
• przez nawroty należy rozumieć:
  -- cofnięcie określania wag
  -- cofnięcie usuwania krawędzi z E
  -- dalszą iterację po krawędziach lub wzięcie innej krawędzi...

Algorytm:

• wybieramy i usuwamy z E krawędź AB

#pierwszy trójkąt

• wybieramy i usuwamy z E krawędź AC
• zakładamy, że AB i AC mają wspólny wierzchołek A
• iterujemy po możliwych wagach A:
  -- obliczając oczekiwaną wartość wierzchołków B i C oraz krawędzi BC
  -- szukamy krawędzi BC (o obliczonej długości) i usuwamy ją z E
  -- określamy wagi wierzchołkom A, B i C

kolejny wierzchołek

• określamy wierzchołek D
• iterując po możliwych wagach wierzchołka D
  -- obliczamy oczekiwane wagi krawędzi AD,BD,CD
  -- poszukujemy w E krawędzi AD,CD,CD (o odpowiednich wagach)
  -- jeśli znaleźliśmy wszystkie to:
  --- usuwamy AD,BD,CD z E i nadajemy D odpowiednią wagę

kolejny wierzchołek

...

Zazwyczaj wagi są nieujemne, czy w tym zadaniu też takie są? Jeśli tak, to łatwo podać przykład braku rozwiązania: jedna krawędź ma wagę 100, pozostałe wagę 1.

Rozwiązanie tylko dla tego przypadku (graf pełen z pięcioma krawędziami). Nazewnictwo wierzchołków zgodnie z wielkością, załóżmy że krawędzie są w posortowanej tablicy t[1..10]. Wiemy, że:
AB -> t[1]
AC -> t[2]
CE -> t[9]
DE -> t[10].
Znając to można łatwo obliczyć Wc-Wb, Wd-Wc oraz Wd-Wb, i następnie dzięki temu pozycję krawędzi AD w tablicy (może być tylko 4 lub 3). Jeżeli krawędź AD jest na czwartej pozycji, to krawędź BC jest na 3 pozycji, znająć jej wartość oraz Wc-Wb policzenie dalej jest trywialne. W innym wypadku krawędź BC może być na 4 lub 5 pozycji, założyłbym obydwie możliwości, dopóki nie dojdzie do sprzeczności w jednym rozwiązaniu.

Albo o wiele prościej. Po zsumowaniu całej tablicy otrzymujemy 4Wa+4Wb+4Wc+4Wd+4*We=Suma, znamy Wa+Wb=T[1] oraz Wd+We=T[10], więc Wc=Suma/4-T[1]-T[10], Wa=T[2]-Wc, Wb=T1-Wa itd.