AlgoVerse

یکریختی گراف (پس‌گرد)

دنبال نگاشتی از رأس‌های یک گراف به دیگری می‌گردد که همه‌ی یال‌ها و نایال‌ها را حفظ کند: رأس به رأس، با پس‌گرد و هرس با درجه‌ها. در بدترین حالت n! حالت.

دو گراف A و B یکریخت‌اند اگر نگاشت یک‌به‌یکی f از رأس‌های A به رأس‌های B باشد که u و v در A مجاور باشند اگر و تنها اگر f(u) و f(v) در B مجاور باشند؛ یعنی همان گراف با برچسب‌های دیگر.

ادامه‌ی توضیح ↓
ورودی:
A 5×5 · B 5×5خروجی PDF

دو دور پنج‌رأسی با شماره‌گذاری متفاوت (۰-۱-۲-۳-۴ و ۰-۲-۴-۱-۳)؛ یکریخت‌اند.

  1. def isomorphic(A, B):
  2. # A and B are adjacency matrices (1 = edge). Look for f: vertices of A -> vertices of B keeping every edge and non-edge.
  3. n = len(A)
  4. if len(B) != n:
  5. return None
  6. deg_a = []
  7. deg_b = []
  8. for i in range(n):
  9. deg_a.append(sum(A[i]))
  10. deg_b.append(sum(B[i]))
  11. if sorted(deg_a) != sorted(deg_b):
  12. return None
  13. f = [-1] * n
  14. used = [False] * n
  15. rows = [[i, "·"] for i in range(n)] # for the picture: vertex of A, its image in B
  16. if extend(0, A, B, f, used, deg_a, deg_b, rows):
  17. return f
  18. return None
  21. def extend(i, A, B, f, used, deg_a, deg_b, rows):
  22. n = len(A)
  23. if i == n:
  24. return True
  25. for j in range(n):
  26. if used[j] or deg_a[i] != deg_b[j]:
  27. continue
  28. ok = True
  29. for k in range(i):
  30. if A[i][k] != B[j][f[k]]:
  31. ok = False
  32. break
  33. if not ok:
  34. continue
  35. f[i] = j
  36. used[j] = True
  37. rows[i][1] = j
  38. if extend(i + 1, A, B, f, used, deg_a, deg_b, rows):
  39. return True
  40. f[i] = -1
  41. used[j] = False
  42. rows[i][1] = "·"
  43. return False

ناوردا: f روی رأس‌های 0 تا i−1 یک‌به‌یک است و هر جفت از آن‌ها در A مجاورند اگر و تنها اگر تصویرهایشان در B مجاور باشند.

شروع اجرا

f—

جدول هنوز خالی است.

درخت فراخوانی‌های بازگشتی

نارنجی پر = فراخوانی در حال اجرا · حاشیه‌ی نارنجی = هنوز روی پشته · خاکستری = تمام شده

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

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

A list

[0, 1, 0, 0, 1][1, 0, 1, 0, 0][0, 1, 0, 1, 0][0, 0, 1, 0, 1][1, 0, 0, 1, 0]

B list

[0, 0, 1, 1, 0][0, 0, 0, 1, 1][1, 0, 0, 0, 1][1, 1, 0, 0, 0][0, 1, 1, 0, 0]

Call stack

  1. isomorphic()خط 1
گام ۱ از ۱۶۶
خط سیاه = map · خط نارنجی = گام کلیدیmap: 0/5 · clash: 0/3 · isomorphic: 0/1
    توضیح

    مسئله

    دو گراف A و B یکریخت‌اند اگر نگاشت یک‌به‌یکی f از رأس‌های A به رأس‌های B باشد که u و v در A مجاور باشند اگر و تنها اگر f(u) و f(v) در B مجاور باشند؛ یعنی همان گراف با برچسب‌های دیگر.

    پس‌گرد

    رأس‌های A را به ترتیب نگاشت می‌کنیم. برای رأس i هر رأس استفاده‌نشده‌ی B با همان درجه را امتحان می‌کنیم و بررسی می‌کنیم با همه‌ی رأس‌های قبلی سازگار باشد (یال در A ⇔ یال در B). اگر به بن‌بست رسیدیم، انتخاب را پس می‌گیریم و بعدی را امتحان می‌کنیم.

    هرس و ناورداها

    پیش از جست‌وجو، ناورداها (چیزهایی که یکریختی حفظشان می‌کند) را مقایسه می‌کنیم: تعداد رأس‌ها و فهرست درجه‌ها. فرق در یک ناوردا یعنی قطعاً یکریخت نیستند؛ ولی یکی بودن همه‌ی آن‌ها کافی نیست (پیش‌تنظیم «درجه‌های یکسان»).

    پیچیدگی

    در بدترین حالت n! نگاشت. الگوریتم چندجمله‌ای شناخته‌شده‌ای نیست، ولی NP-کامل بودنش هم ثابت نشده است (Babai: زمان شبه‌چندجمله‌ای).

    ورودی

    A و B ماتریس‌های مجاورت‌اند (۱ یعنی یال)؛ رأس‌ها از ۰ شماره‌گذاری شده‌اند.