Изоморфизам графова

У теорији графова, изоморфизам графова Г и Х је бијекција измедју чворова Г и Х

$f\colon V(G)\to V(H)\,\!$

таква да било која два чвора у и в из Г су суседни чворови у Г ако и само ако ƒ(у) и ƒ(в) су суседни чворови у Х.

У горњој дефиницији, подразумева се да су графови неусмерени, необележени и да гране немају тежину. Медјутим, нотација изморфизма може бити примењена на све друге варијанте нотације графова, додајући услове који це сачувати одговарајуће додатне елементе структуре: правац, тежину гране, итд., са следећим изузетком. Када се говори о облежавању графова са јединственим ознакама, које обично иду од 1, 2,..., н, где је н број цворова графа, два обелезена графа су изоморфна ако су одговарајуци полазни необелезени графи изоморфни.

Ако постоји изоморфизам измедју два графа, онда кажемо да су графови изоморфни и пишемо $G\simeq H$. У случају да бијекција слика граф у самога себе нпр., када Г и Х представљају исти граф, онда се бијекција назива аутоморфизам од Г.

Изоморфизам графова је релација еквиваленције и као таква, дели класу свих графова у класе еквиваленције. Скуп медјусобно изоморфних графова се зове класа изоморфизама графова.

Пример

Следећа два графу су изоморфна, иако њихови цртежи изгледају потпуно другације.

Граф Г	Граф Х	Изоморфизам између Г и Х
		ф(а) = 1 ф(б) = 6 ф(ц) = 8 ф(д) = 3 ф(г) = 5 ф(х) = 2 ф(и) = 4 ф(ј) = 7

Мотивација

Формална нотација изоморфизма, нпр. изоморфизам графова, обухвата неформалну нотацију да неки објекти имају исту структуру ако се игнорису идивидуалне разлике ситних компоненти објеката у питању. Када год је индивидуалност ситних компоненти (цворови, гране) важна за тачну репрезентацију било чега што је моделовано графовима, модел буде дорадјен додајући додатне услове на структуру.