Grafik boyama
Grafik renklendirme, bir grafiğin köşelerine renk atama işlemi olarak tanımlanabilir. Bunda iki bitişik köşeyi doldurmak için aynı renk kullanılmamalıdır. Grafik renklendirmeye Vertex Coloring de diyebiliriz. Grafik renklendirmede, grafiğin uç noktaları aynı renkle renklendirilmiş herhangi bir kenar içermemesine dikkat etmeliyiz. Bu tür grafikler, Düzgün renkli grafik olarak bilinir.
Grafik renklendirme örneği
Java'da liste oluşturma
Bu grafikte, aşağıda açıklanan uygun şekilde renklendirilmiş grafiği gösteriyoruz:
Yukarıdaki grafik aşağıda açıklanan bazı noktaları içermektedir:
- İki bitişik köşeyi renklendirmek için aynı renk kullanılamaz.
- Dolayısıyla buna düzgün renklendirilmiş bir grafik diyebiliriz.
Grafik renklendirme uygulamaları
Grafik renklendirmenin çeşitli uygulamaları vardır. Önemli uygulamalarından bazıları şu şekilde açıklanmaktadır:
- Atama
- Harita boyama
- Görevlerin zamanlanması
- Sudoku
- Zaman çizelgesini hazırlayın
- Çatışma çözümü
Kromatik Sayı
Kromatik sayı, herhangi bir grafiği uygun şekilde renklendirmek için gereken minimum renk sayısı olarak tanımlanabilir. Başka bir deyişle, kromatik sayı, herhangi bir grafiği, bir grafiğin bitişik iki köşesine aynı renk atanmayacak şekilde renklendirmek için gereken minimum renk sayısı olarak tanımlanabilir.
Kromatik sayı örneği:
Kromatik sayıyı anlamak için aşağıda açıklanan bir grafiği ele alacağız:
Yukarıdaki grafik aşağıda açıklanan bazı noktaları içermektedir:
- İki bitişik köşeyi renklendirmek için aynı renk kullanılmaz.
- Bu grafiğin minimum renk sayısı 3'tür ve bu, köşelerin doğru şekilde renklendirilmesi için gereklidir.
- Dolayısıyla bu grafikte kromatik sayı = 3
- Bu grafiği düzgün bir şekilde renklendirmek istiyorsak bu durumda en az 3 renge ihtiyacımız var.
Kromatik Grafik Sayısı Türleri:
Aşağıda açıklanan çeşitli kromatik sayı grafiği türleri vardır:
Döngü Grafiği:
Bir grafik, 'n' uzunluğunda bir döngü oluşturan 'n' kenar ve 'n' köşe (n >= 3) içeriyorsa döngü grafiği olarak bilinecektir. Döngü grafiğindeki tüm köşelerin yalnızca 2 veya 3 derece derecesi olabilir.
Kromatik sayı:
- Bir döngü grafiğindeki kromatik sayı, eğer o grafikteki köşelerin sayısı çift ise 2 olacaktır.
- Bir döngü grafiğindeki kromatik sayı, eğer o grafikteki köşelerin sayısı tek ise 3 olacaktır.
Döngü grafiği örnekleri:
Döngü grafiklerinin çeşitli örnekleri vardır. Bunlardan bazıları şu şekilde anlatılmaktadır:
Örnek 1: Aşağıdaki grafikte kromatik sayıyı belirlememiz gerekiyor.
Çözüm: Yukarıdaki döngü grafiğinde üç köşe için 3 farklı renk vardır ve bitişik köşelerin hiçbiri aynı renkle renklendirilmemiştir. Bu grafikte köşe sayısı tektir. Bu yüzden
Kromatik sayı = 3
Örnek 2: Aşağıdaki grafikte kromatik sayıyı belirlememiz gerekiyor.
Çözüm: Yukarıdaki döngü grafiğinde dört köşe için 2 renk vardır ve bitişik köşelerin hiçbiri aynı renkle renklendirilmemiştir. Bu grafikte köşe sayısı çifttir. Bu yüzden
Kromatik sayı = 2
Örnek 3: Aşağıdaki grafikte kromatik sayıyı belirlememiz gerekiyor.
Çözüm: Yukarıdaki grafikte beş köşe için 4 farklı renk vardır ve iki bitişik köşe aynı renkle (mavi) renklendirilmiştir. Yani bu grafik bir döngü grafiği değildir ve kromatik bir sayı içermez.
Örnek 4: Aşağıdaki grafikte kromatik sayıyı belirlememiz gerekiyor.
Çözüm: Yukarıdaki grafikte altı köşe için 2 farklı renk vardır ve bitişik köşelerin hiçbiri aynı renkle renklendirilmemiştir. Bu grafikte köşe sayısı çifttir. Bu yüzden
Kromatik sayı = 2
Planlayıcı Grafiği
Bir grafik bir düzlemde çizilirse planlayıcı grafik olarak bilinecektir. Planlayıcı grafiğinin kenarları birbirini kesmemelidir.
Kromatik Sayı:
- Planlayıcı grafiğinde kromatik sayı 4'ten küçük veya 4'e eşit olmalıdır.
- Planlayıcı grafiği, örnek 3 hariç yukarıdaki döngü grafiklerinin tümü ile de gösterilebilir.
Planya grafiği örnekleri:
Planer grafiklerin çeşitli örnekleri vardır. Bunlardan bazıları şu şekilde anlatılmaktadır:
Örnek 1: Aşağıdaki grafikte kromatik sayıyı belirlememiz gerekiyor.
Çözüm: Yukarıdaki grafikte 3 köşe için 3 farklı renk bulunmaktadır ve bu grafiğin hiçbir kenarı birbirini kesmemektedir. Bu yüzden
Java'da 'euler'in numarası'
Kromatik sayı = 3
Burada kromatik sayı 4'ten küçüktür, dolayısıyla bu grafik bir düzlem grafiğidir.
Örnek 2: Aşağıdaki grafikte kromatik sayıyı belirlememiz gerekiyor.
Çözüm: Yukarıdaki grafikte dört köşe için 2 farklı renk bulunmaktadır ve bu grafiğin hiçbir kenarı birbirini kesmemektedir. Bu yüzden
Kromatik sayı = 2
Burada kromatik sayı 4'ten küçüktür, dolayısıyla bu grafik bir düzlem grafiğidir.
Örnek 3: Aşağıdaki grafikte kromatik sayıyı belirlememiz gerekiyor.
Çözüm: Yukarıdaki grafikte 5 köşe için 5 farklı renk bulunmaktadır ve bu grafiğin hiçbir kenarı birbirini kesmemektedir. Bu yüzden
Kromatik sayı = 5
Burada kromatik sayı 4'ten büyüktür, dolayısıyla bu grafik bir düzlem grafiği değildir.
java rastgele matematik rastgele
Örnek 4: Aşağıdaki grafikte kromatik sayıyı belirlememiz gerekiyor.
Çözüm: Yukarıdaki grafikte altı köşe için 2 farklı renk bulunmaktadır ve bu grafiğin hiçbir kenarı birbirini kesmemektedir. Bu yüzden
Kromatik sayı = 2
Burada kromatik sayı 4'ten küçüktür, dolayısıyla bu grafik bir düzlem grafiğidir.
Grafiği Tamamla
Her iki farklı köşeyi birleştirmek için yalnızca bir kenar kullanılıyorsa, bir grafik tam bir grafik olarak bilinecektir. Tam bir grafikteki her köşe diğer her köşeyle bağlantılıdır. Bu grafikte her köşe farklı bir renkle renklendirilecektir. Bu, grafiğin tamamında iki köşenin aynı rengi içermediği anlamına gelir.
Kromatik Sayı
Tam bir grafikte kromatik sayı, o grafikteki köşelerin sayısına eşit olacaktır.
Tam grafik örnekleri:
Tam grafiklerin çeşitli örnekleri vardır. Bunlardan bazıları şu şekilde anlatılmaktadır:
Örnek 1: Aşağıdaki grafikte kromatik sayıyı belirlememiz gerekiyor.
Çözüm: 4 farklı köşe için 4 farklı renk vardır ve yukarıdaki grafikte renklerin hiçbiri aynı değildir. Tanıma göre kromatik sayı, köşelerin sayısıdır. Bu yüzden,
Kromatik sayı = 4
Örnek 2: Aşağıdaki grafikte kromatik sayıyı belirlememiz gerekiyor.
Çözüm: 5 farklı köşe için 5 farklı renk vardır ve yukarıdaki grafikte renklerin hiçbiri aynı değildir. Tanıma göre kromatik sayı, köşelerin sayısıdır. Bu yüzden,
Kromatik sayı = 5
Örnek 3: Aşağıdaki grafikte kromatik sayıyı belirlememiz gerekiyor.
Çözüm: Yukarıdaki grafikte 4 farklı köşe için 3 farklı renk bulunmaktadır ve bir renk iki köşede tekrarlanmaktadır. Yani bu grafik tam bir grafik değil ve kromatik bir sayı içermiyor.
İki Parçalı Grafik
Bir grafik, A ve B olmak üzere iki köşe kümesi içeriyorsa iki parçalı grafik olarak bilinecektir. A'nın köşesi yalnızca B'nin köşeleriyle birleşebilir. Bu, kenarların köşeleri bir kümeyle birleştiremeyeceği anlamına gelir.
Kromatik Sayı
Herhangi iki parçalı grafikte kromatik sayı her zaman 2'ye eşittir.
İki parçalı grafik örnekleri:
İki parçalı grafiklerin çeşitli örnekleri vardır. Bunlardan bazıları şu şekilde anlatılmaktadır:
Örnek 1: Aşağıdaki grafikte kromatik sayıyı belirlememiz gerekiyor.
Çözüm: Yukarıdaki grafikte 2 farklı köşe kümesi vardır. Yani tüm iki parçalı grafiklerin kromatik sayısı her zaman 2 olacaktır.
Kromatik sayı = 2
Ağaç:
Bağlı bir grafik, eğer o grafikte devre yoksa ağaç olarak bilinecektir. Bir ağaçta kaç köşe olursa olsun kromatik sayı 2'ye eşit olacaktır. Her iki parçalı grafik aynı zamanda bir ağaçtır.
Kromatik Sayı
Herhangi bir ağaçta kromatik sayı 2'ye eşittir.
statik java
Ağaç Örnekleri:
Ağacın çeşitli örnekleri vardır. Bunlardan bazıları şu şekilde anlatılmaktadır:
Örnek 1: Aşağıdaki ağaçta kromatik sayıyı belirlememiz gerekiyor.
Çözüm: Dört köşe için 2 farklı renk vardır. Herhangi bir sayıda köşesi olan bir ağaç, yukarıdaki ağaçta 2 olan kromatik sayıyı içermelidir. Bu yüzden,
Kromatik sayı = 2
Örnek 2: Aşağıdaki ağaçta kromatik sayıyı belirlememiz gerekiyor.
Çözüm: Beş köşe için 2 farklı renk vardır. Herhangi bir sayıda köşesi olan bir ağaç, yukarıdaki ağaçta 2 olan kromatik sayıyı içermelidir. Bu yüzden,
Kromatik sayı = 2
Kromatik Sayının gerçek hayattan örneği
Diyelim ki Marry Xyz Şirketinde bir yönetici. Şirket bazı yeni çalışanları işe alıyor ve bu yeni çalışanlar için bir eğitim programı hazırlaması gerekiyor. Üç toplantıyı planlamak zorunda ve toplantılar için mümkün olduğunca az sayıda zaman aralığını kullanmaya çalışıyor. İki farklı toplantıya katılmak zorunda olan bir çalışan varsa yöneticinin bu toplantılar için farklı zaman çizelgelerini kullanması gerekir. Bu toplantının görsel bir temsilini elde etmek istediğimizi varsayalım.
Görsel temsil için Marry, toplantıyı belirtmek amacıyla noktayı kullanır. İki toplantısı olan ve her iki toplantıya da katılmak isteyen bir çalışan varsa bu durumda her iki toplantı da bir kenar yardımıyla birbirine bağlanacaktır. Farklı zaman dilimleri renkler yardımıyla temsil edilir. Böylece yönetici, iki nokta aynı kenarı paylaşan aynı rengi içermeyecek şekilde noktaları bu renklerle doldurur. (Bu, iki toplantıya katılması gereken çalışanın aynı zaman diliminde olmaması gerektiği anlamına gelir). Bunun görsel temsili şu şekilde anlatılmaktadır:
