در گراف ساده، وزن‌دار و بی‌جهت ‎$G$‎، هر یالِ ‎$(u‎, ‎v)$‎، دارای یک ‎«وزن»‎ است که می‌تواند مثبت، منفی، یا صفر باشد و با ‎$w(u,v)$‎ نمایش می‌دهیم. هم‌چنین هر رأسِ ‎$u$‎، یک ‎«عددِ علامت»‎ دارد که فقط می‌تواند ‎$+1$‎ یا ‎$-1$‎ باشد و با ‎$p(u)$‎ نشان داده می‌شود. وزن یال‌ها از قبل تعیین شده است، ولی عدد علامت رأس‌ها را ما می‌توانیم تعیین کنیم.

پس از تعیین عدد علامت رأس‌ها، ‎«ارزش»‎ هر یالِ ‎$(u‎, ‎v)$‎ که آن را با ‎$q(u,v)$‎ نمایش می‌دهیم، به این صورت محاسبه می‌شود: $$ q(u‎, ‎v) = p(u) \times w(u‎, ‎v) \times p(v) $$‎ برای هر رأسِ ‎$u$‎، ‎ «ثروت»‎ آن را با ‎$C(u)$‎ نشان می‌دهیم که حاصل جمع ارزش یال‌های متصل به آن است یا به عبارت دیگر: $$ C(u) = \sum_{v \in N(u)} {q(u‎, ‎v)} $$‎. ثابت کنید به‌ازای هر گراف اوّلیه‌ی ‎$G$‎، می‌توان عدد علامت تمام رأس‌ها را طوری تعیین کرد که ثروت هیچ رأسی منفی نشود.

• سوال بعد
• سوال قبل