«Գրաֆների տեսություն»–ի խմբագրումների տարբերություն

[[File:Petersen Wagner minors.svg|thumb|360px| [[Պետերսենի գրաֆ]]ը հարթ չէ: Այն պարունակում է ինչպես ''K''<sub>5</sub> մինոր (ձախից), այնպես էլ ''K''<sub>3,3</sub> մինոր (աջից): Պետերսենի գրաֆը պատկերված է փոքր գագաթներով և սև կողերով: Դեղին գույնով նշված են մինորները:]]
 
Գրաֆների տեսության հետաքրքիր խնդիրներից է '''ենթագրաֆների իզոմորֆիզմի խնդիրը''', երբ տրված գրաֆում անհրաժեշտ է պարզել որոշակի [[ենթագրաֆ]]ի գոյությունը: Այս խնդիրները կարևորվում են այն պատճառով, որ գրաֆների բազմաթիվ հատկանիշներ (հարթ լինելը, երկկողմանի լինելը և այլն) '''ժառանգական''' են ենթագրաֆների նկատմամբ, այսինքն տրված գրաֆը բավարարում է այդ հատկությանը այն և միայն այն դեպքում, երբ նրա բոլոր ենթագրաֆները ևս բավարարում են նույն հատկությանը: Սակայն, որոշակի ենթագրաֆների գոյությունը պարզելը հաճախ բարդ խնդիր է: Մասնավորապես, տրված գրաֆում ամենամեծ [[լրիվ|լրիվ գրաֆ]] ենթագրաֆի գտնելը [[NP-լրիվ խնդիր]] է<ref>Մեծագույն լրիվ ենթագրաֆի հզորությունը կոչվում է clique number: Ավելի մանրամասն՝ [http://mathworld.wolfram.com/CliqueNumber.html Wolfram MathWorld: Clique Number]</ref>:
 
Նման խնդիրներ դրվում են նաև [[ծնված ենթագրաֆ]]ների համար: Այս խնդիրներն էլ հաճախ բարդ են: Օրինակ, տրված գրաֆում մեծագույն [[անկախ բազմություն]] գտնելու խնդիրը (այսինքն, մեկուսացված գագաթներով ծնված ենթագրաֆ գտնելը) նույնպես NP-լրիվ է: