Processing math: 7%

المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۱۷:تئوری:سوال ۳

سوال ۳

در گراف ساده، وزن‌دار و بی‌جهت ‎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‎، می‌توان عدد علامت تمام رأس‌ها را طوری تعیین کرد که ثروت هیچ رأسی منفی نشود.


ابزار صفحه