離散数学におけるグラフ同型性

同型グラフは、単一のグラフが複数の形式を持つことができるグラフとして説明できます。つまり、2 つの異なるグラフが同じ数のエッジ、頂点、および同じエッジ接続を持つことができるということです。このようなタイプのグラフは、同型グラフとして知られています。同型グラフの例は次のように説明されます。

上のグラフには次のことが含まれています。

同じグラフが複数の形式で表現されます。
したがって、これらのグラフは同型グラフであると言えます。

グラフ同型性の条件

次の 4 つの条件を満たす場合、任意の 2 つのグラフは同型写像として知られます。

指定されたグラフには同じ数の頂点が存在します。
指定されたグラフには同じ数のエッジが存在します。
指定されたグラフには、同じ量の次数シーケンスが存在します。
最初のグラフが頂点 {v1、v2、v3、... を利用して長さ k のサイクルを形成しているとします。 vk} の場合、別のグラフも頂点 {v1、v2、v3、... を使用して同じ長さ k の同じサイクルを形成する必要があります。 vk}。

注: グラフの度数シーケンスは、すべての頂点の度数を昇順で並べたものとして説明できます。

注意事項

任意の 2 つのグラフが同型であるために必要な条件は、上で定義した 4 つの条件です。
与えられたグラフが同型であることを示すのに、上で定義した条件が十分である必要はありません。
2 つのグラフが上で定義した 4 つの条件を満たす場合でも、グラフが確実に同型である必要はありません。
グラフがどの条件も満たさない場合、そのグラフは確実に同型ではないと言えます。

グラフ同型性の十分条件

任意の 2 つのグラフが同型であることを証明したい場合、2 つのグラフが確実に同型であることを保証する十分条件がいくつかあります。 2 つのグラフが上記の 4 つの条件をすべて正常にクリアした場合にのみ、それらのグラフが十分な条件を満たしているかどうかがチェックされます。これについては次のように説明します。

両方のグラフの補グラフが同型である場合、これらのグラフは確実に同型になります。
両方のグラフの隣接する行列が同じである場合、これらのグラフは同型になります。
1 つのグラフのいくつかの頂点を削除することで 2 つのグラフの対応するグラフが得られ、他の画像の対応する画像が同型である場合にのみ、これらのグラフは同型ではなくなります。

2 つのグラフが上記の条件のいずれかを満たしている場合、それらのグラフは確実に同型であると言えます。

グラフの同型性の例

グラフの同型性の例は数多くあり、次のように説明されています。

例 1:

この例では、次のグラフが同型かどうかを示しました。

解決： このために、次のように説明されるグラフ同型性の 4 つの条件をすべてチェックします。

条件1:

グラフ 1 では、合計 4 つの頂点の数、つまり G1 = 4 があります。
グラフ 2 では、合計 4 つの頂点の数、つまり G2 = 4 があります。

ここ、

グラフ G1 と G2 の両方に同じ数の頂点があります。したがって、これらのグラフは条件 1 を満たしています。次に、2 番目の条件を確認します。

条件2:

グラフ 1 には、エッジの数が合計 5 つあります。つまり、G1 = 5 です。
グラフ 2 には、合計 6 個のエッジがあります (G2 = 6)。

ここ、

グラフ G1 と G2 の両方に同じ数のエッジはありません。したがって、これらのグラフは条件 2 を満たしていません。残りの条件をすべて確認することはできません。

これらのグラフは条件 2 に違反しているため、これらのグラフは同型ではありません。

∴グラフG1とグラフG2は同型グラフではありません。

例 2:

この例では、次のグラフが同型かどうかを示しました。

解決： このために、次のように説明されるグラフ同型性の 4 つの条件をすべてチェックします。

条件1:

グラフ 1 では、合計 4 つの頂点の数、つまり G1 = 4 があります。
グラフ 2 では、合計 4 つの頂点の数、つまり G2 = 4 があります。
グラフ 3 では、合計 4 つの頂点の数、つまり G3 = 4 があります。

ここ、

すべてのグラフ G1、G2、および G3 には同じ数の頂点があります。したがって、これらのグラフは条件 1 を満たしています。次に、2 番目の条件を確認します。

条件2:

グラフ 1 には、エッジの数が合計 5 つあります。つまり、G1 = 5 です。
グラフ 2 には、エッジの数が合計 5 つあります。つまり、G2 = 5 です。
グラフ 3 には、エッジの数が合計 4 つあります。つまり、G2 = 4 です。

ここ、

グラフ G1 と G2 の両方に同じ数のエッジがあります。したがって、これらのグラフは条件 2 を満たしています。
ただし、グラフ (G1、G2) と G3 には同じ数のエッジがありません。したがって、グラフ (G1、G2) と G3 は条件 2 を満たしていません。

したがって、グラフ (G1、G2) と G3 は条件 2 に違反します。したがって、これらのグラフは同型ではないと言えます。

∴ グラフ G3 は、グラフ G1 またはグラフ G2 と同型ではありません。

グラフ G1 と G2 は条件 2 を満たしているため、これらのグラフは同型である可能性があると言えます。

∴グラフ G1 と G2 は同型である可能性があります。

コンピューターネットワーク

次に、グラフ G1 と G2 の 3 番目の条件を確認します。

条件3:

グラフ 1 では、シーケンスの次数 s は {2, 2, 3, 3}、つまり G1 = {2, 2, 3, 3} です。
グラフ 2 では、系列の次数 s は {2, 2, 3, 3}、つまり G2 = {2, 2, 3, 3} です。

ここ

グラフ G1 と G2 の両方に同じ数の次数シーケンスがあります。したがって、これらのグラフは条件 3 を満たしています。次に、4 番目の条件を確認します。

条件4:

グラフ G1 は、頂点 {2, 3, 3} を使用して長さ 3 のサイクルを形成します。

グラフ G2 も、頂点 {2, 3, 3} を使用して長さ 3 のサイクルを形成します。

ここ、

これは、グラフ G1 と G2 が頂点 {2, 3, 3} を利用して長さ 3 のサイクルを形成しているため、両方のグラフに同じサイクルが含まれていることを示しています。したがって、これらのグラフは条件 4 を満たしています。

したがって、

グラフ G1 と G2 は、上記 4 つの必要条件をすべて満たしています。
したがって、G1 と G2 は同型である可能性があります。

ここで、グラフ G1 と G2 が同型であることを示すための十分条件を確認します。

十分条件の確認

両方のグラフの補グラフが同型である場合、2 つのグラフは確実に同型となることがわかりました。

そこで、次のように説明される G1 と G2 の補数グラフを描画します。

上記の G1 と G2 の補数グラフでは、両方のグラフが同型であることがわかります。

∴ グラフ G1 と G2 は同型写像です。

例 3:

この例では、次のグラフが同型かどうかを示しました。

解決： このために、次のように説明されるグラフ同型性の 4 つの条件をすべてチェックします。

条件1:

グラフ 1 では、頂点の数は合計 8 つ、つまり G1 = 8 です。
グラフ 2 には、頂点の数が合計 8 つあります。つまり、G2 = 8 です。

ここ、

グラフ G1 と G2 の両方に同じ数の頂点があります。したがって、これらのグラフは条件 1 を満たしています。次に、2 番目の条件を確認します。

条件2:

グラフ 1 では、エッジの総数は 10、つまり G1 = 10 です。
グラフ 2 では、エッジの総数は 10、つまり G2 = 10 です。

ここ、

グラフ G1 と G2 の両方に同じ数のエッジがあります。したがって、これらのグラフは条件 2 を満たしています。次に、3 番目の条件を確認します。

条件3:

グラフ 1 では、シーケンスの次数 s は {2, 2, 2, 2, 3, 3, 3, 3}、つまり G1 = {2, 2, 2, 2, 3, 3, 3, 3} です。。
グラフ 2 では、シーケンスの次数 s は {2, 2, 2, 2, 3, 3, 3, 3}、つまり G2 = {2, 2, 2, 2, 3, 3, 3, 3} です。。

ここ

nginx変数

条件4:

グラフ G1 は、次数 3 の頂点を使用して長さ 4 のサイクルを形成します。
グラフ G2 は、頂点が隣接していないため、頂点を利用して長さ 4 のサイクルを形成していません。

ここ、

グラフＧ１とグラフＧ２はいずれも、同じ長さの同じ周期を形成していない。したがって、これらのグラフは条件 4 に違反します。

グラフ G1 と G2 は条件 4 に違反しているため、条件 4 に違反しているため、これらのグラフは同型ではありません。

∴グラフ G1 と G2 は同型ではありません。