20
BAB III GRAF BERARAH BARIS-BERHINGGA
Pada bab ini akan dibahas konsep-konsep pada graf berarah. Lebih lanjut, akan dibahas juga lintasan berhingga, lintasan tak hingga, dan himpunan silinder beserta contohnya. 3.1 Graf Berarah Berikut ini akan dibahas graf berarah, graf berarah baris-berhingga dan produk dari graf berarah Definisi 3.1.1: Graf Berarah (Raeburn, 2005: 5) Sebuah graf berarah 1.
terdiri dari pasangan
merupakan himpunan terhitung (countable) yang unsur-unsurnya disebut titik.
2.
merupakan himpunan terhitung (countable) yang unsur-unsurnya disebut sisi.
3.
merupakan dua fungsi yang disebut fungsi range dan source, ,
4. Jika
merupakan source dari dan
,
dan
merupakan range dari .
adalah sebuah sisi dari
ke
Azico Sudhagama, 2014 Topologi kompak lokal hausdorff Pada ruang lintasan tak hingga Universitas Pendidikan Indonesia | repository.upi.edu | perpustakaan.upi.edu
.
Contoh 3.1.2 Diberikan
dan dan
, dengan , ilustrasi dari graf
,
dapat diberikan seperti gambar
𝑣 𝑒
𝑓
𝑢
𝑤
𝑔
Definisi 3.1.3: Graf Berarah Baris-Berhingga (Raeburn, 2005: 6) Sebuah graf berarah
disebut baris-berhingga, jika setiap titiknya menerima paling
banyak berhingga sisi, yaitu, dimana berhingga untuk setiap
adalah himpunan
.
Contoh 3.1.4 Diberikan
merupakan himpunan tak hingga dan
gabungan dari himpunan tunggal
𝑣
𝑣2
merupakan
, maka dapat diilustrasikan sebagai berikut
… 𝑣3
𝑣4
𝑣5
Definisi 3.1.5: Produk dari Graf Berarah (Johnston & Reynolds: 2009)
21
Azico Sudhagama, 2014 Topologi kompak lokal hausdorff Pada ruang lintasan tak hingga Universitas Pendidikan Indonesia | repository.upi.edu | perpustakaan.upi.edu
Produk dari graf berarah , dimana
dan dan
adalah graf didefinisikan sebagai berikut:
Untuk setiap (
)
(
)
Contoh 3.1.6 Diberikan graf berarah , dan graf
dengan
,
dengan
,
dimana dimana
Maka graf
dan , dimana
, , dan (
)
(
)
(
)
(
)
Graf
(
)
(
)
dapat diilustrasikan sebagai berikut 𝑣 𝑤
𝑣 𝑥
𝑢𝑤
𝑢𝑥
22
dan
Azico Sudhagama, 2014 Topologi kompak lokal hausdorff Pada ruang lintasan tak hingga Universitas Pendidikan Indonesia | repository.upi.edu | perpustakaan.upi.edu
.
3.2 Lintasan Pada Graf Berarah Berikut ini akan dibahas konsep lintasan berhingga dan lintasan tak hingga pada sebuah graf berarah, dan juga akan dibahas himpunan silinder. Definisi 3.2.1: Lintasan Berhingga (Raeburn, 2005: 9) Lintasan dengan panjang sisi-sisi di
dari graf berarah
sedemikian sehingga
Selanjutnya dituliskan | |
…
merupakan barisan untuk
untuk panjang dari
himpunan dari lintasan-lintasan dengan panjang
.
dari
.
. Himpunan
merupakan
dapat diilustrasikan sebagai
berikut
𝜇
𝜇2
…
𝜇3
𝜇𝑛
Dari ilustrasi tersebut, diperoleh 2 2 3
…
2
2 3
2 3
…
2 3 4
…
2
2…
Selanjutnya definisikan source ke dan
⋃
. Kemudian, kita perluas pemetaan range dan
dengan menetapkan untuk
dan . 23
Azico Sudhagama, 2014 Topologi kompak lokal hausdorff Pada ruang lintasan tak hingga Universitas Pendidikan Indonesia | repository.upi.edu | perpustakaan.upi.edu
| |
untuk | |
,
Jika
dan
lintasan
merupakan lintasan-lintasan dengan …
| |
…
untuk
| |.
Untuk himpunan dari titik-titik
dan himpunan dari lintasan-lintasan
kita definisikan jika
, kita tulis
dan
, kita notasikan
,
. Selanjutnya,
yang artinya
dan
untuk
.
Definisi 3.2.2: Lintasan Tak Hingga (KPRR, 1997: 5) Lintasan tak hingga
dari graf berarah
sedemikian sehingga Jika lintasan-lintasan lintasan
…
| |
untuk dan
…
merupakan barisan .
dengan
, kita tulis
himpunan dari titik-titik
dengan menetapkan
dan untuk
, kita definisikan
Ilustrasi lintasan tak hingga dari graf berarah
.
sebagai berikut …
𝜇2
𝜇4
𝜇3
Definisi 3.2.3: Himpunan Silinder (Webster, 2010: 12) Untuk
untuk
….
Kita perluas pemetaan range ke
𝜇
…
, kita definisikan himpunan silinder dari
24
oleh
Azico Sudhagama, 2014 Topologi kompak lokal hausdorff Pada ruang lintasan tak hingga Universitas Pendidikan Indonesia | repository.upi.edu | perpustakaan.upi.edu
Himpunan silinder dari lintasan
adalah lintasan
yang berada di
, dimana
merupakan faktor dari . Ilustrasi dari himpunan silinder sebagai berikut
𝜇
…
… 𝜇2
𝜇𝑛
𝜈′ 𝜈′′
…
Dari ilustrasi tersebut, dapat dilihat bahwa terdapat barisan ′ ′2 … sedemikian sehingga membentuk barisan baru
25
…
Azico Sudhagama, 2014 Topologi kompak lokal hausdorff Pada ruang lintasan tak hingga Universitas Pendidikan Indonesia | repository.upi.edu | perpustakaan.upi.edu
′ ′ .
dan
