شکل ظاهری را موقتاً کنار بگذار
چرخش، کشیدن یا جابهجایی رأسها ساختار اتصال را عوض نمیکند. نام رأس و محل هندسی را با نقش ساختاری آن یکی ندان؛ سؤال اصلی این است که کدام رأسها به هم متصلاند.
تعداد رأس و یال را اول کنترل کن
اگر این دو شمار برابر نیستند، گرافها نمیتوانند همریخت باشند و نیازی به جستوجوی نگاشت نیست. برابری آنها فقط شرط اولیه است و همریختی را بهتنهایی ثابت نمیکند.
تعداد رأس | تعداد یال | دنبالهٔ درجهها | رأسهای جدا یا آویزان | مؤلفهها | دورهای شاخص | الگوی همسایگی
درجهها را مرتب و مقایسه کن
درجهٔ همهٔ رأسها را بنویس و فهرست را مرتب کن. تفاوت در دنبالهٔ درجهها دلیل کافی برای ناهمریختی است؛ برابر بودن دنباله هنوز ممکن است برای اثبات کافی نباشد.
رأسهای نقشدار را پیدا کن
رأس یکتای دارای بیشترین درجه، رأس آویزان یا رأس متصل به چند رأس خاص میتواند نقطهٔ شروع نگاشت باشد. ابتدا رأسهایی را جفت کن که نقش ساختاری مشابه دارند.
همسایههای رأسهای ویژه را مقایسه کن
فقط درجهٔ رأس مرکزی را نبین؛ درجه و ارتباط همسایههایش را نیز بررسی کن. دو رأس همدرجه ممکن است در محیط محلی متفاوتی قرار داشته باشند و نتوانند متناظر شوند.
دورها و فاصلهها را شاهد کمکی بگیر
وجود دور با طول مشخص، تعداد مؤلفهها یا فاصلهٔ میان رأسهای ویژه میتواند تفاوت ساختار را نشان دهد. ویژگیای را انتخاب کن که در هر دو گراف تعریف و قابل مقایسه باشد.
برای اثبات همریختی نگاشت کامل بساز
نام هر رأس گراف اول را روبهروی یک رأس گراف دوم بنویس. نگاشت باید یکبهیک و پوشا باشد و ارتباط هر زوج متناظر را حفظ کند. چند تطابق درستِ ابتدایی اثبات کامل نیست.
یالها را تحت نگاشت کنترل کن
فهرست یالهای گراف اول را از راه نگاشت به زوجهای گراف دوم تبدیل کن و وجود همهٔ آنها را بررسی کن. در صورت نیاز نایالهای تعیینکننده را نیز کنترل کن تا اتصال اضافی پنهان نماند.
برای ناهمریختی یک تفاوت کافی پیدا کن
لازم نیست همهٔ نگاشتهای ممکن را رد کنی. یک ناوردای متفاوت یا تناقض ناگزیر در همسایگی کافی است. تفاوت ظاهری رسم یا نام رأسها دلیل ساختاری محسوب نمیشود.
ماتریس را ابزار مقایسه کن
ماتریسهای مجاورت با ترتیب متفاوت رأسها ممکن است ظاهر متفاوتی داشته باشند. اگر نگاشت پیشنهادی داری، سطرها و ستونها را هماهنگ بازچین و ارتباطها را بسنج. برای ساخت ماتریس از راهنمای ماتریس مجاورت استفاده کن.