PEDIA: Konektivitas pada Digraph |

<p><br />
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in; text-align: justify;">
<b><span style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">D. Konektivitas Tiap Jenis Graph</span></b><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in; text-align: justify;">
<b><span style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">a. </span></b><b><span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">Konektivitas
pada Undigraph</span></b><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in; text-align: justify; text-indent: -.25in;">
<span lang="IN" style="color: #262626; font-family: Symbol; font-size: 10.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">·</span><span lang="IN" style="color: #262626; font-family: "Times New Roman","serif"; font-size: 7.0pt; mso-ansi-language: IN; mso-fareast-font-family: "Times New Roman";">         </span><span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">Adjacency: Dua verteks <i>x</i> dan <i>y</i> yang
berlainan disebut berhubungan langsung (adjacent) jika terdapat sisi {<i>x</i>, <i>y</i>}
dalam E.</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in; text-align: justify; text-indent: -.25in;">
<span lang="IN" style="color: #262626; font-family: Symbol; font-size: 10.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">·</span><span lang="IN" style="color: #262626; font-family: "Times New Roman","serif"; font-size: 7.0pt; mso-ansi-language: IN; mso-fareast-font-family: "Times New Roman";">         </span><span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">Path: Sederetan verteks yang mana setiap verteks adjacent
dengan verteks yang tepat berada disebelahnya.</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in; text-align: justify; text-indent: -.25in;">
<span lang="IN" style="color: #262626; font-family: Symbol; font-size: 10.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">·</span><span lang="IN" style="color: #262626; font-family: "Times New Roman","serif"; font-size: 7.0pt; mso-ansi-language: IN; mso-fareast-font-family: "Times New Roman";">         </span><span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">Panjang dari path: jumlah sisi yang dilalui path.</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in; text-align: justify; text-indent: -.25in;">
<span lang="IN" style="color: #262626; font-family: Symbol; font-size: 10.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">·</span><span lang="IN" style="color: #262626; font-family: "Times New Roman","serif"; font-size: 7.0pt; mso-ansi-language: IN; mso-fareast-font-family: "Times New Roman";">         </span><span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">Siklus: suatu path dengan panjang lebih dari satu yang
dimulai dan berakhir pada suatu verteks yang sama.</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in; text-align: justify; text-indent: -.25in;">
<span lang="IN" style="color: #262626; font-family: Symbol; font-size: 10.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">·</span><span lang="IN" style="color: #262626; font-family: "Times New Roman","serif"; font-size: 7.0pt; mso-ansi-language: IN; mso-fareast-font-family: "Times New Roman";">         </span><span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">Siklus sederhana: dalan undigraph, siklus yang terbentuk
pada tiga atau lebih verteks-verteks yang berlainan yang mana tidak ada verteks
yang dikunjungi lebih dari satu kali kecuali verteks awal/akhir.</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in; text-align: justify; text-indent: -.25in;">
<span lang="IN" style="color: #262626; font-family: Symbol; font-size: 10.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">·</span><span lang="IN" style="color: #262626; font-family: "Times New Roman","serif"; font-size: 7.0pt; mso-ansi-language: IN; mso-fareast-font-family: "Times New Roman";">         </span><span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">Dua verteks <i>x</i> dan <i>y</i> yang
berbeda dalam suatu undigraph disebut berkoneksi (connected) apabila jika
terdapat path yang menghubungkannya.</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in; text-align: justify; text-indent: -.25in;">
<span lang="IN" style="color: #262626; font-family: Symbol; font-size: 10.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">·</span><span lang="IN" style="color: #262626; font-family: "Times New Roman","serif"; font-size: 7.0pt; mso-ansi-language: IN; mso-fareast-font-family: "Times New Roman";">         </span><span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">Himpunan bagian verteks S disebut terkoneksi (connected)
apabila dari setiap verteks <i>x</i> dalam S terdapat path ke setiap
verteks <i>y</i> (<i>y</i> bukan <i>x</i>) dalam S.</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in; text-align: justify; text-indent: -.25in;">
<span lang="IN" style="color: #262626; font-family: Symbol; font-size: 10.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">·</span><span lang="IN" style="color: #262626; font-family: "Times New Roman","serif"; font-size: 7.0pt; mso-ansi-language: IN; mso-fareast-font-family: "Times New Roman";">         </span><span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">Suatu komponen terkoneksi (connected components) adalah
subgraph (bagian dari graph) yang berisikan satu himpunan bagian verteks yang
berkoneksi.</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in; text-align: justify; text-indent: -.25in;">
<span lang="IN" style="color: #262626; font-family: Symbol; font-size: 10.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">·</span><span lang="IN" style="color: #262626; font-family: "Times New Roman","serif"; font-size: 7.0pt; mso-ansi-language: IN; mso-fareast-font-family: "Times New Roman";">         </span><span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">Suatu undigraph dapat terbagi atas beberapa komponen yang
terkoneksi; jika terdapat lebih dari satu komponen terkoneksi maka tidak
terdapat path dari suatu verteks dalam satu komponen verteks di komponen
lainnya.</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in; text-align: justify; text-indent: -.25in;">
<span lang="IN" style="color: #262626; font-family: Symbol; font-size: 10.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">·</span><span lang="IN" style="color: #262626; font-family: "Times New Roman","serif"; font-size: 7.0pt; mso-ansi-language: IN; mso-fareast-font-family: "Times New Roman";">         </span><span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">Pohon bebas (free tree): suatu undigraph yang hanya
terdapat satu komponen terkoneksi serta tidak memiliki siklus sederhana.</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span><br />
<div style="text-align: center;">
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">

</span></div>
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";"><br /></span></div>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in; text-align: justify;">
<b><span style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">b. </span></b><b><span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">Konektivitas
pada Digraph</span></b><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in; text-align: justify; text-indent: .5in;">
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">Terminologi
di atas berlaku juga pada Digraph kecuali dalam digraph harus dikaitkan dengan
arah tertentu karena pada arah yang sebaliknya belum tentu terdefinisi.</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in; text-align: justify; text-indent: -.25in;">
<span lang="IN" style="color: #262626; font-family: Symbol; font-size: 10.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">·</span><span lang="IN" style="color: #262626; font-family: "Times New Roman","serif"; font-size: 7.0pt; mso-ansi-language: IN; mso-fareast-font-family: "Times New Roman";">         </span><span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">Adjacency ke / dari: Jika terdapat sisi (<i>x</i>,<i>y</i>)
maka dalam digraph dikatakan bahwa <i>x</i> "adjacent
ke" <i>y</i> atau <i>y</i> "adjacent
dari" <i>x</i>. Demikian pula jika terdapat path dari <i>x</i> ke <i>y</i> maka
belum tentu ada path dari <i>y</i> ke <i>x</i> Jadi dalam
digraph keterkoneksian didefinisikan lebih lanjut lagi sebagai berikut.</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in; text-align: justify; text-indent: -.25in;">
<span lang="IN" style="color: #262626; font-family: Symbol; font-size: 10.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">·</span><span lang="IN" style="color: #262626; font-family: "Times New Roman","serif"; font-size: 7.0pt; mso-ansi-language: IN; mso-fareast-font-family: "Times New Roman";">         </span><span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">Terkoneksi dengan kuat: Himpunan bagian verteks S
dikatakan terkoneksi dengan kuat (strongly connected) bila setiap pasangan
verteks berbeda <i>x</i> dan <i>y</i> dalam S, <i>x</i> berkoneksi
dengan <i>y</i> dan <i>y</i> berkoneksi dengan <i>x</i> (dpl.,
ada path dari <i>x</i> ke <i>y</i> dan sebaliknya
dari <i>y</i> ke <i>x</i>).</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in; text-align: justify; text-indent: -.25in;">
<span lang="IN" style="color: #262626; font-family: Symbol; font-size: 10.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">·</span><span lang="IN" style="color: #262626; font-family: "Times New Roman","serif"; font-size: 7.0pt; mso-ansi-language: IN; mso-fareast-font-family: "Times New Roman";">         </span><span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">Terkoneksi dengan Lemah: Himpunan bagian verteks S
dikatakan terkoneksi dengan lemah (weakly connected) bila setiap pasangan
verteks berbeda <i>x</i> dan <i>y</i> dalam S, salah
satu: <i>x</i> berkoneksi dengan <i>y</i> (atau <i>y</i> berkoneksi
dengan <i>x</i>) dan tidak kebalikan arahnya (dpl., hanya terdefinisi satu
path: dari <i>x</i> ke <i>y</i> atau sebaliknya dari <i>y</i> ke <i>x</i>).</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span><br />
<div style="text-align: center;">
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">

</span></div>
</div>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in; text-align: justify; text-indent: -.25in;">
<br /></div>
</p>

D. Konektivitas Tiap Jenis Graph a. Konektivitas pada Undigraph · Adjacency: Dua verteks x dan y yang berlainan disebut...