Граф төбелері дәрежелерінің қосындысы - Тұжырым ("қол алысу туралы лемма»)
- Графтың барлық төбелерінің қосындысы-екі еселенген қабырғалар санына тең жұп сан:
- Лемманың түсіндірмесі: әр қол алысуда екі қол қатысатын болғандықтан, кез келген қол алысудағы алысқан қолдың жалпы саны жұп болады (әр қол қанша рет қол алысуға қатысса, сонша рет саналады). Салдар
- Кез келген графта тақ дәрежедегі төбелер саны жұп болады.
Графтар изоморфизмі - G1 мен G2 екі графы изоморфты болады, егер G1 мен G2 графтарының сәйкес қабырғалары сәйкес төбелеріне инцидентті болып, қабырғалар мен төбелер жиындарының арасында өзара бірмәнділік беунелеуі болса.
- Егер G графы Rn -дегі G' геометриялық графына изоморфты болса, онда G’ G графының Rn кеңістігіндегі геометриялық орындалуы деп аталады.
- R2 графы - R3 графының геометриялық орындалуы.
Изоморфты графтарға мысал - Төбелердің сәйкестігі: v1v2’,v2v3’,v3v1’,v4v4’,v5v5’;
- Қабырғалардың сәйкестігі :
- e1e1’, e3e2’, e5e4’, e2e5’, e4e6’, e6e3’.
- G1 мен G2 – изоморфты графтар
Изоморфизм графтар жиынындағы эквиваленттік қатынас ретінде - Изоморфизмнің қатынасы эквивалентті болып табылады, яғни ол симметриялы, транзитивті және рефлексивті.
Белгіленген және абстрактілі графтар - n ретті граф белгіленген деп аталады, егер оның төбелеріне кейбір белгілер берілсе (мысалы, 1, 2, …, n нөмірлері).
- Абстрактілі (немесе белгіленбеген) граф – бұл изоморфты графтар класы.
Достарыңызбен бөлісу: |