Question 1

Graf nasıl tanımlanır?

Accepted Answer

Matematiksel anlamda Graf, düğümler ve bu düğümler arasındaki ilişkileri gösteren kenarlardan oluşan kümeye verilen isimdir.

Question 2

Yönlü ve yönsüz Graf nasıl tanımlanır?

Accepted Answer

Düğümler arasındaki kenarlara yönlendirme atanan graflara Yönlü Graf, yönlendirme olmayan durumdaki graflara ise Yönsüz Graf adı verilmektedir.

Question 3

Graflarda kenarlar hangi işlevi görür?

Accepted Answer

Kenarlar, iki düğümü birleştirerek düğümler arasındaki ilişkiyi meydana getirmektedirler.

Question 4

Ağırlıksız graf nasıl tanımlanır?

Accepted Answer

Sadece iki düğümün bağlı olup olmaması önemseniyorsa böyle bir graf ağırlıksız olarak adlandırılır.

Question 5

Komşu düğümler nasıl tanımlanır?

Accepted Answer

Verilen bir G grafı üzerinde tanımlı di ve dj iki düğüm, kenar kümesinde tanımlı bir kenar ile ilişkilendiriliyorsa bu iki düğüm, komşu (adjacent) düğümlerdir.

Question 6

Yönlendirilmiş graf nasıl tanımlanır?

Accepted Answer

Bir G grafı üzerinde tanımlanmış kenarlar, düğümler arasındaki bağlantıların nerede başlayıp nerede bittiğini gösteren yönlendirme bilgisine sahip ise bu graflara yönlendirilmiş/yönlü graf denmektedir.

Question 7

Yönlü ya da yönsüz graflarda kenar nasıl temsil edilir?

Accepted Answer

Yönsüz graflarda, kenardaki düğümlerin sırası önemli olmadığından bir kenar {v,w} veya {w,v} olarak temsil edilebilir. Bununla birlikte yönlendirilmiş kenar (v,w), v’nin kenarın kuyruğu yani başlangıç noktası ve w’nin kenarın başı yani bitiş noktası olduğunu simgelemektedir.

Question 8

Grafik teorisinde basit yol nedir?

Accepted Answer

Grafik teorisinde basit yol, bir grafta tekrar eden düğümleri olmayan bir yola verilen addır.

Question 9

Bir grafta tekrar eden düğümleri olmayan bir yola ne ad verilir?

Accepted Answer

Grafik teorisinde basit yol, bir grafta tekrar eden düğümleri olmayan bir yola verilen addır.

Question 10

Grafiği eksantrikliği nedir?

Accepted Answer

Eksantriklik, bir tepe noktasının diğer tepe noktasından maksimum uzaklığı olarak tanımlanmaktadır. Bir tepe noktasının diğer tüm tepe noktalarına olan maksimum uzaklığı, o tepe noktasının eksantrikliği olarak kabul edilir ve e(V) ile gösterilir.

Question 11

Grafın çap değeri nasıl bulunur?

Accepted Answer

Grafın çapı, düğüm çifti arasındaki maksimum mesafedir. Grafın çap değerinin bulunması için tüm yollar bulunur ve sonra hepsinin maksimum değeri hesaplanır. Ayrıca tüm düğümlerden mak- simum eksantriklik değerleri bulunarak da grafın çap bilgisi elde edilebilir.

Question 12

Şekildeki grafta 2 numaralı düğümün komşuluk listesi nasıldır?

Accepted Answer

2 numaralı düğümün komşuluk listesi 1,3,4 şeklindedir.

Question 13

Önce Derinlik Araması ne amaçla kullanılır?

Accepted Answer

Önce Derinlik Araması veya Önce Derinlik Geçişi, bir grafiğin veya ağaç veri yapısının tüm düğüm- lerini aramak için kullanılan yinelemeli (recursive) bir algoritmadır.

Question 14

DFS algoritması hangi amaçlarla kullanılır?

Accepted Answer

DFS Algoritması Yol (path) bulmak için Grafiğin ikili yani 2 parça olup olmadığını test etmek için Bir grafiğin güçlü bir şekilde bağlantılı bileşenlerini bulmak için Bir grafikteki döngüleri tespit etmek için kullanılmaktadır.

Question 15

BFS algoritması hangi adımlarla çalışır?

Accepted Answer

BFS algoritma şu şekilde çalışmaktadır:

1. Grafın düğümlerinden herhangi birini kuyruğun sonuna ekleyerek başlayın.

2. Kuyruğun ilk ögesini alın ve ziyaret edilenler listesine ekleyin.

3. Bu düğümün bitişik düğümlerinin bir listesini oluşturun. Ziyaret edilenler listesinde olmayanları sıranın en arkasına ekleyin.

4. Kuyruk boşalana kadar 2. ve 3. adımları tekrarlamaya devam edin adımlarından oluşur.

Question 16

BFS algoritmasının amacı nedir?

Accepted Answer

BFS a lgoritma sı nın amacı, döngülerden kaçınırken her düğümü ziyaret edilmiş olarak işaretlemektir.

Question 17

BFS algoritmasının zaman karmaşıklığı nasıl ifade edilir?

Accepted Answer

BFS algoritmasının zaman karmaşıklığı, D’nin düğüm sayısı ve K’nin kenar sayısı olduğu O(D + K) şeklinde temsil edilir.

Question 18

BFS algoritması hangi amaçlarla kullanılır?

Accepted Answer

BFS Algoritması Yol bulma algoritmaları GPS navigasyonu için Arama dizinine göre dizin oluşturmak için bir ağda maksimum akışı bulmak amacıyla Ford- Fulkerson algoritmasında Yönsüz bir grafikte döngü algılama Minimum yayılan ağaç (Minimum Spanning Tree) gibi alanlarda kullanılmaktadır.

Question 19

DFS ve BFS algoritmaları arasındaki temel farklar nelerdir?

Accepted Answer

DFS ve BFS algoritmaları arasındaki temel farklar şu şekildedir: DFS, kenar tabanlı bir algoritma iken BFS, düğüm tabanlı bir algoritma olarak tasarlanmıştır. DFS yığın veri yapısı veya özyineleme kullanırken BFS’de kuyruk veri yapısı kullanılmıştır. DFS’de bellek alanı daha verimli bir şekilde kullanılırken BFS’de bellek alanının verimli şekilde kullanımı göz ardı edilmektedir. BFS en uygun algoritma iken DFS en uygun değildir. DFS, dar ve uzun ağaçlar oluştururken BFS, geniş ve kısa bir ağaç oluşturmaktadır.

Question 20

DFS ve BFS algoritmalarında bellek kullanımı nasıldır?

Accepted Answer

DFS’de bellek alanı daha verimli bir şekilde kullanılırken BFS’de bellek alanının verimli şekilde kullanımı göz ardı edilmektedir.

Veri Yapıları — Ünite 8 Soru-Cevap