În teoria grafurilor, un grafic de potrivire este un grafic care poate fi desenat pe un plan în așa fel încât toate muchiile sale să fie segmente de linie de lungimea unu și muchiile să nu se intersecteze. Astfel, acest grafic are o încorporare în plan atât ca un grafic de distanță unitară , cât și ca un grafic plan . Informal vorbind, un grafic de potrivire poate fi așezat prin potriviri care nu se intersectează pe o suprafață plană , de unde și numele [1] .
Multe cercetări privind graficele chibrituri se referă la graficele obișnuite în care fiecare vârf are același număr de vecini. Acest număr se numește gradul graficului.
Se știe că există grafice de potrivire de toate gradele până la al patrulea. Graficele complete cu unul, două și trei vârfuri (un singur vârf, o muchie și un triunghi) sunt grafice de chibrit, 0-, 1- și, respectiv, 2-regulate. Cel mai mic grafic cu 3 chibrituri obișnuite este format din două copii de romburi situate astfel încât vârfurile corespunzătoare să fie la distanța unitară. Învelișul său dublu bipartit este graficul unei prisme octogonale cu intersecții [1] .
În 1986, Heiko Harbort l-a prezentat pe conte, care și-a primit numele - Earl of Harbort . Cu 104 muchii și 52 de vârfuri, acest grafic este cel mai mic exemplu cunoscut de grafic de potrivire cu 4- obișnuite [2] . Graficul este rigid [3] .
Este imposibil ca un grafic de potrivire obișnuit să aibă un grad mai mare de patru [4] .
Așa cum arată Kurtz și Mazukolo [5] , cel mai mic grafic cu 3 triunghiuri regulate fără chibrituri (circum ≥ 4) are 20 de vârfuri. În plus, au prezentat cel mai mic exemplu cunoscut de grafic cu 3 chibrituri obișnuite cu circumferința 5 (180 de vârfuri).
Verificarea dacă un anumit graf planar nedirecționat poate fi reprezentat ca un graf chibrit este o problemă NP-hard [6] [7]
Numărul de grafice de potrivire diferite (până la izomorfism) este cunoscut până la zece muchii [8] [9] :
1, 1 , 3 , 5 , 12 , 28 , 74 , 207, 633, 2008, …