Pairwise compatibility graph
આલેખ સિદ્ધાંતમાં, આલેખ એ જોડી મુજબ સુસંગતતા આલેખ (પી. સી. જી.) છે જો ત્યાં એક વૃક્ષ અને બે બિન-નકારાત્મક વાસ્તવિક સંખ્યાઓ અસ્તિત્વમાં હોય, જેમ કે દરેક નોડમાં એક-થી-એક મેપિંગ હોય, જેમાં બે નોડ હોય અને જો અને માત્ર વચ્ચેનું અંતર અંતરાલમાં હોય તો જ તેને અડીને હોય. પી. સી. જી. ના પેટા વર્ગોમાં મહત્તમ સાત શિરોબિંદુઓ, ચક્રો, જંગલો, સંપૂર્ણ આલેખ, અંતરાલ આલેખ અને નિસરણી આલેખનો સમાવેશ થાય છે. જો કે, આઠ શિરોબિંદુઓ સાથે એક આલેખ છે જે પી. સી. જી. તરીકે જાણીતો નથી. ફિલોજેનેટિક્સ સાથેનો સંબંધ જોડી મુજબ સુસંગતતા આલેખ સૌપ્રથમ પોલ કેર્ની, જે. ઇયાન મુનરો અને ડેરેક ફિલિપ્સ દ્વારા ફિલોજેની પુનર્નિર્માણના સંદર્ભમાં રજૂ કરવામાં આવ્યા હતા. ફિલોજેનેટિક વૃક્ષમાંથી નમૂના લેતી વખતે, આપેલ લંબાઈ વચ્ચે પાથ અંતર ધરાવતા ગાંઠો શોધવાનું કાર્ય સંકળાયેલ પી. સી. જી. માં જૂથ શોધવાની સમકક્ષ છે. જટિલતા ગ્રાફને પી. સી. જી. તરીકે ઓળખવાની ગણતરીની જટિલતા 2020 સુધી અજ્ઞાત છે. જો કે, ગ્રાફ અને બિન-ધાર સંબંધોની પસંદગી માટે શોધવાની સંબંધિત સમસ્યા એ છે કે પી. સી. જી. સબગ્રાફ તરીકે ધરાવે છે અને જેમાં કોઈ પણ ધાર નથી, તે એન. પી.-હાર્ડ તરીકે ઓળખાય છે. વૃક્ષમાં ગાંઠો શોધવાનું કાર્ય કે જેના માર્ગોનું અંતર અને વચ્ચે હોય છે તે બહુપદી સમયમાં ઉકેલવા યોગ્ય હોવાનું જાણીતું છે. તેથી, જો વૃક્ષને બહુપદી સમયમાં પી. સી. જી. માંથી પુનઃપ્રાપ્ત કરી શકાય, તો પી. સી. જી. પર જૂથની સમસ્યા પણ બહુપદી હશે. 2020 સુધીમાં, આમાંથી કોઈ પણ જટિલતાઓ જાણીતી નથી. સંદર્ભો આલેખ પરિવારો કોમ્પ્યુટેશનલ ફિલોજેનેટિક્સ