İnteraktif Dersler

Ağlar: parçalar, güzergâhlar ve ağırlıklar

Ders notları

Tanım

Ağ: düğümler ve kenarlar

Ağ, noktalardan ve çizgilerden oluşan bir şekildir. Noktalar düğümlerdir; iki düğüm arasındaki çizgi bir kenardır. Bir ağ; bir metro haritasını, arkadaşlıkları, yolları ya da bir okulun koridorlarını gösterebilir. Parçalar sekmesinde kenarları yazarsın, örneğin A-B, B-C, ya da bir durum seçersin; uygulama düğümleri ve kenarları sayar.
Örnek
A-B, A-C, B-C, C-D, D-E ağında 5 düğüm (A, B, C, D ve E) ve 5 kenar var.
ABCDE5 vertices, 5 edges
Kural

Derecelerin toplamı kenar sayısının iki katıdır

Bir düğümün derecesi, o düğümde biten kenar sayısıdır. Her kenarın iki ucu vardır; bu yüzden bütün dereceleri topladığında her kenar iki kez sayılır. Derecelerin toplamı her zaman kenar sayısının iki katıdır ve her zaman çifttir. Parçalar sekmesi dereceleri ve toplamlarını gösterir.
Örnek
Dereceler 2, 2, 3, 2 ve 1 → ve kenar. Toplam 13 olamaz, çünkü tektir.
A2B2C3D2E1Degrees: 2, 2, 3, 2, 1
Tanım

Parçalar ve çevrimler

Her düğümden diğer her düğüme kenarlar boyunca gidebiliyorsan ağ tek parçadır. Gidemiyorsan ağın ayrı parçaları vardır. Çevrim, hiçbir düğümü iki kez kullanmadan başladığı yere dönen bir turdur. Parçalar sekmesi kaç parça olduğunu ve çevrim olup olmadığını söyler.
Örnek
A-B, B-C, A-C, D-E ve tek başına bir F düğümü 3 parça verir: A, B, C; sonra D, E; ve tek başına F. A, B ve C bir çevrim oluşturur: A − B − C − A.
ABCDEF3 separate parts
Tanım

Güzergâhlar: bir yol bir düğümden iki kez geçmez

Bir güzergâh (yol), kenarlar boyunca bir düğümden başka bir düğüme gider ve hiçbir düğümden iki kez geçmez. A düğümünden F düğümüne giden güzergâhları saymak için A düğümünden çıkan her ilk adımı izle ve hiçbir düğümden iki kez geçme. Güzergâhlar sekmesinde Başlangıç ve Varış değerlerini seçersin, kaç güzergâh olduğunu görürsün ve Güzergâh ile hepsini gezersin; liste önce en az kenarlı güzergâhları gösterir.
Örnek
A-B, A-C, B-C, C-D, D-E, E-F, D-F ağında A düğümünden F düğümüne 4 güzergâh var: 2 tanesi A − B ile, 2 tanesi A − C ile başlar. En kısası 3 kenarlı A − C − D − F; en uzunu 5 kenarlı A − B − C − D − E − F.
ABCDEFA − C − D − F: 3 edges
Tanım

Ağırlıklı ağ ve toplam ağırlık

Ağırlıklı bir ağda her kenarın bir ağırlığı vardır: bir uzaklık, bir süre ya da bir maliyet. Ağırlığı iki nokta üst üsteden sonra yazarsın: A-B:4. Bir güzergâhın toplam ağırlığı, kenarlarının ağırlıkları toplamıdır. Ağırlıklar sekmesinde ağırlıklar kenarların üzerindeki küçük kutularda görünür.
Örnek
A-B:4, B-C:3, C-D:5, B-E:6, E-F:2, D-F:4, C-E:7 metro ağında A − B − C − D − F güzergâhının toplamı . A − B − C − E − F güzergâhının toplamı da .
4356247ABCDEFA − B − C − D − F: 4 + 3 + 5 + 4 = 16
Kural

En küçük toplam, adım adım

En küçük toplamı bulmak için her güzergâhı yazmak zorunda değilsin. İlk düğümden 0 toplamıyla başla. Henüz kesinleşmemiş düğümler arasında toplamı en küçük olan kesinleşir. Komşularının toplamlarını güncelle: daha küçük bir toplam daha büyüğün yerini alır. Bunu tekrarla. Ağırlıklar sekmesindeki En iyi toplam ve Durum (kesin ya da geçici) tablosu bunu adım adım gösterir.
Örnek
Metro ağında A düğümünden: A 0; B 4; C 7 ; E 10 (, C üzerinden değerinden daha iyi); D 12 ; F 12 . A düğümünden F düğümüne en küçük toplam 12, A − B − E − F güzergâhında.
4356247ABCDEFA − B − E − F: 4 + 6 + 2 = 12
Dikkat!

En az kenar her zaman en ucuz değildir

En az kenarlı güzergâhın toplamı, daha uzun bir güzergâhın toplamından büyük olabilir. En kısa görünen güzergâhta durma: güzergâhların ağırlıklarını topla ve karşılaştır. Ağırlıklar sekmesi en az kenarlı güzergâhın toplamını gösterir ve en küçük toplamdan ne kadar fazla olduğunu söyler.
Örnek
A-B:2, B-C:2, A-C:7, C-D:1 ağında A düğümünden D düğümüne: A − C − D güzergâhında 2 kenar var ve toplam . A − B − C − D güzergâhında 3 kenar var ve toplam ; bu, 3 daha az.
2271ABCDA − B − C − D: 2 + 2 + 1 = 5
Püf noktası

Ağ yazmak ve tuşlar

Kenarları aralarına virgül koyarak yaz, örneğin A-B, B-C. Tek başına bir harf, kenarı olmayan bir düğümdür. A ile H arasındaki harfleri kullan; en çok 12 kenar olabilir. Ağırlık iki nokta üst üsteden sonra yazılır, örneğin A-B:4; ya her kenarın ağırlığı olmalı ya da hiçbirinin. 4 hazır durum var. Yazdığın hiçbir şey kaydedilmez ya da bir yere gönderilmez. Her sayı kutusu, seçenek ve düğme klavyeyle çalışır.
Örnek
A-B:4, B-C:3, C-D olmaz, çünkü C-D kenarının ağırlığı yok. A-B:4, B-C:3, C-D:5 olur.

Alıştırmalar

A-B, A-C, B-C, C-D, D-E ağında C düğümünün derecesi kaçtır? Kolay
ABCDEThe network of the question
Çözümü göster
Derece, C düğümündeki kenar sayısıdır. C düğümünde biten kenarları say: A-C, B-C ve C-D.
Bunlar 3 kenardır.
3
Düğümün her kenarını bir kez say. A-B kenarı hem A hem B için sayılır.
Bir ağın 6 düğümü var ve dereceleri 3, 3, 2, 2, 2 ve 2. Bu ağın kaç kenarı var? Kolay
Çözümü göster
Dereceleri topla → .
Her kenarın iki ucu vardır, bu yüzden iki kez sayılmıştır → kenar.
7 kenar
14 deme: bu derecelerin toplamıdır ve her kenar iki kez sayılmıştır.
Bunlardan hangisi A-B, A-C, B-C, C-D, D-E ağında bir güzergâhtır: A − C − D − E, A − B − D − E ya da A − C − B − C? Kolay
Çözümü göster
Her adımı kontrol et: iki harf arasında kenar var mı ve bir harf iki kez geçiyor mu?
A − B − D − E: B-D bir kenar değil. A − C − B − C: C iki kez geçiyor. A − C − D − E: A-C, C-D ve D-E birer kenar ve hiçbir düğüm iki kez geçmiyor.
A − C − D − E
Bir güzergâh yalnızca ağın kenarlarını kullanır ve hiçbir düğümden iki kez geçmez.
A-B, A-C, B-C, C-D, D-E, E-F, D-F ağında A düğümünden F düğümüne kaç güzergâh var? Orta
ABCDEFFrom A to F
Çözümü göster
A düğümünden çıkan ilk adımı izle. B üzerinden: A − B − C ve sonra D düğümüne. C üzerinden: A − C ve sonra D düğümüne. Hiçbir düğümden iki kez geçme.
D düğümünden F düğümüne doğrudan (D-F) ya da E üzerinden (D − E − F) gidilir. B üzerinden 2, C üzerinden 2 güzergâh var: A − C − D − F, A − B − C − D − F, A − C − D − E − F ve A − B − C − D − E − F.
güzergâh.
4 güzergâh
Aramayı ilk adıma göre sıralamak yardımcı olur: böylece hiçbir güzergâhı unutmaz ve hiçbirini iki kez saymazsın.
A-B:4, B-C:3, C-D:5, B-E:6, E-F:2, D-F:4, C-E:7 metro ağında A − B − C − E − F güzergâhının toplam ağırlığı kaçtır? Orta
4356247ABCDEFThe metro: weights in minutes
Çözümü göster
Güzergâhın her kenarının ağırlığını oku: A-B 4, B-C 3, C-E 7 ve E-F 2.
Hepsini topla → .
16
Son adımı farklı bir güzergâhın toplamı aynı olabilir: A − B − C − D − F güzergâhı da 16.
Aynı metro ağında A düğümünden F düğümüne giden bir güzergâhın en küçük toplam ağırlığı kaçtır ve hangi güzergâhtır? Orta
4356247ABCDEFA − B − E − F: 4 + 6 + 2 = 12
Çözümü göster
A düğümünden 0 ile başla. B düğümü 4 alır. C düğümü alır. E düğümü alır; bu, C üzerinden değerinden daha iyidir.
D düğümü alır. F düğümü E üzerinden alır; D üzerinden olurdu.
En küçük toplam 12, A − B − E − F güzergâhında → .
12, A − B − E − F güzergâhında
Burada en az kenarlı güzergâh (3 kenar) aynı zamanda en ucuzdur, ama bu bir rastlantıdır, kural değil.
A-B:2, B-C:2, A-C:7, C-D:1 ağında A düğümünden D düğümüne en az kenarlı güzergâh, toplam ağırlığı en küçük güzergâhtan ne kadar daha pahalıdır? Zor
2271ABCDFrom A to D
Çözümü göster
En az kenar: 2 kenarlı A − C − D. Toplamı .
Diğer güzergâh 3 kenarlı A − B − C − D; toplamı .
Fark .
3
Burada yalnızca iki güzergâh var; doğrudan karşılaştırabilirsin. Daha çok güzergâh varsa A düğümünden adım adım ilerle.
Bir ağın 6 düğümü var ve her düğümün derecesi 3. Kaç kenarı var? 5 düğümün hepsinin derecesi 3 olan bir ağ olabilir mi? Zor
Çözümü göster
Derecelerin toplamı . Bu, kenar sayısının iki katıdır; yani kenar var.
5 düğümle toplam olurdu. Derecelerin toplamı kenar sayısının iki katı, yani çift olmalı; 15 ise tek.
9 kenar; hayır, olamaz
Derecelerin toplamı hiçbir zaman tek olmaz: derecesi tek olan düğümlerin sayısı her zaman çifttir.
A-B:20, B-C:35, A-D:30, B-D:15, D-E:25, C-E:10 okul koridorlarında B düğümünden E düğümüne en küçük toplamı ve toplamı ikinci en küçük olan güzergâhı bul. Zor
203530152510ABCDEB − D − E: 15 + 25 = 40
Çözümü göster
B düğümünden E düğümüne güzergâhları yaz: B − D − E, B − C − E ve B − A − D − E.
Toplamları → , ve .
En küçük toplam 40, B − D − E güzergâhında; ikincisi 45, B − C − E güzergâhında
Her güzergâhı bulduğunu kontrol et: B-A, B-C ya da B-D ile başlamak burada hepsini kapsar.

Bu konunun etkileşimli uygulamaları

Ücretsiz uygulamalar ücretsiz öğrenci hesabıyla açılır. Öğretmenler tüm uygulamaları canlı derste kullanabilir.

Ücretsiz hesap ve Plus hakkında

Öğretmen misiniz?

Bu uygulamalarla tüm sınıfınıza canlı ders verin. İlk bir ay ücretsiz.

Ücretsiz deneyin

Bu sınıf düzeylerine uygun

IB (MYP, Diploma): MYP 4, MYP 5, Diploma, 1. yıl, Diploma, 2. yıl

Cambridge International: AS Level, A Level

İngiltere (GCSE, A Level): Year 12 (A Level), Year 13 (A Level)

Bu konunun uygulamaları neler öğretir 1 uygulama

Ağlar: parçalar, güzergâhlar ve ağırlıklar

  • Ağı yazıp köşelerini, kenarlarını ve derecelerini okuma
  • İki köşe arasındaki rotaları sayma ve en az kenarlı olanı bulma
  • En az toplam ağırlıklı rotayı bulma