Граф төбелері дәрежелерінің қосындысы

Граф төбелері дәрежелерінің қосындысы

• Тұжырым ("қол алысу туралы лемма»)
• Графтың барлық төбелерінің қосындысы-екі еселенген қабырғалар санына тең жұп сан:
• Лемманың түсіндірмесі: әр қол алысуда екі қол қатысатын болғандықтан, кез келген қол алысудағы алысқан қолдың жалпы саны жұп болады (әр қол қанша рет қол алысуға қатысса, сонша рет саналады). Салдар
• Кез келген графта тақ дәрежедегі төбелер саны жұп болады.

Графтар изоморфизмі

• G1 мен G2 екі графы изоморфты болады, егер G1 мен G2 графтарының сәйкес қабырғалары сәйкес төбелеріне инцидентті болып, қабырғалар мен төбелер жиындарының арасында өзара бірмәнділік беунелеуі болса.
• Егер G графы Rn -дегі G' геометриялық графына изоморфты болса, онда G’ G графының Rn кеңістігіндегі геометриялық орындалуы деп аталады.

• R3

• R2

• R2 графы - R3 графының геометриялық орындалуы.

Изоморфты графтарға мысал

• Төбелердің сәйкестігі: v1v2’,v2v3’,v3v1’,v4v4’,v5v5’;
• Қабырғалардың сәйкестігі :
• e1e1’, e3e2’, e5e4’, e2e5’, e4e6’, e6e3’.

• G1 мен G2 – изоморфты графтар

• G1 G2

Изоморфизм графтар жиынындағы эквиваленттік қатынас ретінде

• Изоморфизмнің қатынасы эквивалентті болып табылады, яғни ол симметриялы, транзитивті және рефлексивті.

Белгіленген және абстрактілі графтар

• n ретті граф белгіленген деп аталады, егер оның төбелеріне кейбір белгілер берілсе (мысалы, 1, 2, …, n нөмірлері).
• Абстрактілі (немесе белгіленбеген) граф – бұл изоморфты графтар класы.

• Белгіленген графтар :