İndeks

Bu məsələdə biz $n$ ədədinin iki bölgüsünü nəzərdən keçiririk: \lambda = a_1 + a_2 + \dots + a_k və \mu = b_1 + b_2 + \dots + b_l. Hər bir bölgü, aşağıdakı qaydaya görə $n$ zirvədən ibarət qrafda müəyyən kənarlar yaradır:

Birinci bölgü üçün, $1$ və a_1, $2$ və a_1-1 və s. zirvələri birləşdirilir. Əgər a_1 təkdirsə, ortadakı zirvə tək qalır və birləşdirilmir. İkinci bölgü üçün isə, oxşar şəkildə, a_1+1 və a_1+a_2, a_1+2 və a_1+a_2-1 və s. zirvələr birləşdirilir. İkinci bölgüyə uyğun olan kənarlar da eyni qayda ilə əlavə olunur (qrafda bir neçə kənar bir-birinin üstündə düşə bilər).

Məsələn, əgər n = 10, \lambda = 3+4+2+1 və \mu = 3+5+2 olarsa, onda nəticədə yaranan qrafda $1$ və $3$ zirvələri arasında iki kənar, $4$ zirvəsi $7$ və $8$ ilə, $5$ isə $6$ və $7$ ilə, $6$ yalnız $5$ ilə, $7$ isə $4$ və $5$ ilə, $8$ isə $4$ və $9$ ilə, $9$ isə $8$ və $10$ ilə, $10$ isə yalnız $9$ ilə birləşəcək.

Vitya, iki bölgünün indeksi ilə maraqlanır, bu isə 2b + a şəklində təyin olunur; burada $a$ qrafdakı zəncirlərin, $b$ isə halqaların sayıdır. Zəncir — elə bağlı komponentdir ki, zirvələri elə sıralamaq olar ki, hər ardıcıl cüt arasında bir kənar var və başqa kənar yoxdur. Halqa — zəncirdir, sonuncu və birinci zirvə arasında əlavə bir kənar da var. Bağlı komponent — elə bir bağlı altqrafdır ki, ona heç bir yeni zirvə əlavə etdikdə bağlılıq pozular. Tənha zirvə də zəncir sayılır.

Yuxarıdakı nümunədə, qrafda bir halqa ($1$ və $3$ zirvələrindən ibarət) və iki zəncir var: $(2)$ və (6, 5, 7, 4, 8, 9, 10). Deməli, bu bölgü cütlüyünün indeksi $4$-dür.