رنگ‌آمیزی حریصانه‌ی گراف

حریصانه

گره‌ها را به ترتیب درجه (ولش–پاول) برمی‌دارد و به هر کدام کوچک‌ترین رنگی را می‌دهد که همسایه‌هایش ندارند.

رنگ‌آمیزی گراف یعنی به هر گره رنگی بدهیم که هیچ دو همسایه‌ای هم‌رنگ نباشند (مثلاً زمان‌بندی امتحان‌ها: درس‌هایی که دانشجوی مشترک دارند هم‌زمان نباشند). پیدا کردن کمترین تعداد رنگ (عدد رنگی) NP-سخت است؛ روش حریصانه سریع است ولی همیشه بهینه نیست.

ادامه‌ی توضیح ↓

زمان: O(V log V + E)
حافظه: O(V)
گریمالدی، فصل ۱۱
جانسون‌باو، فصل ۸

ورودی:

V=7 · E=10 · src=Aخروجی PDF

هفت گره؛ گره‌های پرهمسایه اول رنگ می‌شوند و سه رنگ کافی است.

def greedy_coloring(graph, src):
# Welsh-Powell: colour the nodes with the most neighbours first.
order = sorted(graph, key=lambda v: -len(graph[v]))
color = {v: 0 for v in graph}
for u in order:
used = set()
for v, _ in graph[u]:
if color[v] != 0:
used.add(color[v])
c = 1
while c in used:
c = c + 1
color[u] = c
return color

ناوردا: هیچ دو گره‌ی همسایه‌ای که هر دو رنگ گرفته‌اند هم‌رنگ نیستند.

شروع اجرا

گره‌ی جاری (u)
درخت کوتاه‌ترین مسیر تا اینجا
یالِ در حال بررسی

متغیرهای محلی

src'A'

نارنجی = در همین گام عوض شد

graph dict

'A': [('B', 1), ('C', 1)]
'B': [('A', 1), ('C', 1), ('D', 1)]
'C': [('A', 1), ('B', 1), ('D', 1), ('E', 1)]
'D': [('B', 1), ('C', 1), ('F', 1)]
'E': [('C', 1), ('F', 1), ('G', 1)]
'F': [('D', 1), ('E', 1), ('G', 1)]
'G': [('E', 1), ('F', 1)]

Call stack

greedy_coloring()خط 1

گام ۱ از ۱۱۳

رشد تعداد عملیات با اندازه‌ی ورودی

میانگین ۵ گراف تصادفی برای هر n (با seed ثابت). نشانگر توخالی = ورودی فعلی.

look
ورودی فعلی (n=7)

نمایش به شکل جدول

n	look
4	10.4
8	27.6
12	41.6
16	56
20	70.8
24	74.4
28	94.4

توضیح

ایده

الگوریتم

گره‌ها را به ترتیب درجه، از زیاد به کم، مرتب کن (ولش–پاول).
هر گره را به ترتیب بردار و کوچک‌ترین رنگی را بده که هیچ همسایه‌ی رنگ‌شده‌اش ندارد.

حداکثر Δ + 1 رنگ مصرف می‌شود (Δ بیشترین درجه است).

در trace به چه چیزی نگاه کنی

عدد کنار هر گره شماره‌ی رنگ آن است (۰ یعنی هنوز رنگ نشده).
ورودی «ترتیب بد» را ببین: گرافی که با دو رنگ رنگ می‌شود، با ترتیب بد چهار رنگ می‌گیرد.