Teori Grafik - Konektivitas

Apakah mungkin untuk melintasi suatu graf dari satu simpul ke simpul lainnya ditentukan oleh bagaimana sebuah graf terhubung. Konektivitas adalah konsep dasar dalam Teori Graf. Konektivitas menentukan apakah grafik terhubung atau terputus. Ini memiliki subtopik berdasarkan edge dan vertex, yang dikenal sebagai konektivitas tepi dan konektivitas vertex. Mari kita bahas secara detail.

Konektivitas

Sebuah grafik dikatakan connected if there is a path between every pair of vertex. Dari setiap simpul ke simpul lainnya, harus ada beberapa jalur untuk dilintasi. Itu disebut konektivitas grafik. Grafik dengan beberapa simpul dan tepi terputus dikatakan terputus.

Example 1

Pada grafik berikut, adalah mungkin untuk melakukan perjalanan dari satu simpul ke simpul lainnya. Misalnya, seseorang dapat melintasi dari simpul 'a' ke simpul 'e' menggunakan jalur 'ab-e'.

Example 2

Dalam contoh berikut, berpindah dari simpul 'a' ke simpul 'f' tidak dimungkinkan karena tidak ada jalur di antara keduanya secara langsung atau tidak langsung. Karenanya ini adalah grafik yang terputus.

Potong Vertex

Misalkan 'G' adalah grafik yang terhubung. Sebuah simpul V ∈ G disebut simpul potong dari 'G', jika 'G-V' (Hapus 'V' dari 'G') menghasilkan graf yang terputus. Menghapus titik potong dari grafik akan memecahnya menjadi dua grafik atau lebih.

Note - Menghapus titik potong dapat membuat grafik terputus.

Sebuah graf terhubung 'G' mungkin memiliki paling banyak (n – 2) simpul yang terpotong.

Example

Pada grafik berikut, simpul 'e' dan 'c' adalah simpul yang dipotong.

Dengan menghilangkan 'e' atau 'c', grafik akan menjadi grafik yang terputus.

Tanpa 'g', tidak ada jalur antara simpul 'c' dan simpul 'h' dan banyak lainnya. Oleh karena itu, ini adalah grafik yang terputus dengan simpul potong sebagai 'e'. Demikian pula, 'c' juga merupakan titik potong untuk graf di atas.

Cut Edge (Bridge)

Misalkan 'G' adalah grafik yang terhubung. Sisi 'e' ∈ G disebut sebagai tepi potong jika 'G-e' menghasilkan grafik yang tidak terhubung.

Jika menghilangkan tepi dalam grafik menghasilkan dua atau lebih grafik, maka tepi itu disebut Tepi Potong.

Example

Pada grafik berikut, tepi potongnya adalah [(c, e)].

Dengan menghilangkan tepi (c, e) dari grafik, itu menjadi grafik yang terputus.

Pada grafik di atas, menghilangkan sisi (c, e) memecah grafik menjadi dua yang tidak lain adalah grafik terputus. Oleh karena itu, tepi (c, e) adalah tepi potong grafik.

Note - Misalkan 'G' adalah graf terhubung dengan simpul 'n', lalu

tepi potong e ∈ G jika dan hanya jika tepi 'e' bukan bagian dari siklus apa pun di G.
jumlah maksimum tepi potong yang memungkinkan adalah 'n-1'.
setiap kali ada tepi potong, simpul potong juga ada karena setidaknya satu simpul dari sisi potong adalah simpul potong.
jika ada titik potong, maka tepi potong mungkin ada atau tidak.

Potong Set Grafik

Misalkan 'G' = (V, E) adalah graf terhubung. Himpunan bagian E 'dari E disebut himpunan potongan G jika penghapusan semua tepi E' dari G membuat G terputus.

Jika menghapus sejumlah tepi dari suatu grafik membuatnya terputus, maka tepi yang dihapus tersebut disebut set potong grafik.

Example

Perhatikan grafik berikut. Set potongannya adalah E1 = {e1, e3, e5, e8}.

Setelah menghapus set cut E1 dari grafik, akan muncul sebagai berikut -

Demikian pula, ada set potongan lain yang dapat memutuskan grafik -

E3 = {e9} - Kumpulan grafik terkecil.
E4 = {e3, e4, e5}

Konektivitas Tepi

Misalkan 'G' adalah grafik yang terhubung. Jumlah minimum tepi yang pemindahannya membuat 'G' terputus disebut konektivitas tepi G.

Notation - λ (G)

Dengan kata lain, file number of edges in a smallest cut set of G disebut konektivitas tepi G.

Jika 'G' memiliki cut edge, maka λ (G) adalah 1. (konektivitas edge G.)

Example

Perhatikan grafik berikut. Dengan menghilangkan dua tepi minimum, grafik yang terhubung menjadi terputus. Sehingga konektivitas edge-nya (λ (G)) adalah 2.

Berikut adalah empat cara untuk memutuskan grafik dengan menghilangkan dua sisi -

Konektivitas Vertex

Misalkan 'G' adalah grafik yang terhubung. Jumlah minimum simpul yang penghapusannya membuat 'G' terputus atau mengurangi 'G' menjadi grafik trivial disebut konektivitas simpulnya.

Notation - K (G)

Example

Pada grafik di atas, menghilangkan simpul 'e' dan 'i' membuat grafik terputus.