ریاضی را حرف بزن · دانشگاه

گراف: نقطه‌ها، خط‌ها و شمردن گام‌ها

گراف تعدادی نقطه است که با خط به هم وصل شده‌اند: ساده‌ترین تصویر برای هر چیز پیوسته، از مسیرهای یک پارک تا دوستی‌ها تا اینترنت. یک جدول کوچک از صفر و یک می‌تواند همهٔ تصویر را نگه دارد.

پیش‌نویس: نوشتهٔ یک دستیار هوش مصنوعی؛ هنوز معلمی آن را بررسی نکرده است.

الفبا

هر نماد را همان‌طور که زیرش نوشته شده بلند بخوان.

$G = (V, E), ∣ V ∣, ∣ E ∣$ بخوان: G برابر است با V و E؛ اندازهٔ V، اندازهٔ Eیعنی: گراف G مجموعهٔ V از رأس‌ها (نقطه‌ها) و مجموعهٔ E از یال‌ها (خط‌ها) است؛ میله‌های دو طرف تعدادشان را می‌شمارند.
$de g v$ بخوان: درجهٔ vیعنی: تعداد یال‌هایی که به رأس v می‌رسند.
$u \sim v$ بخوان: u با v مجاور استیعنی: u و v با یک یال به هم وصل‌اند: همسایه‌اند.
$v_{۰} \sim v_{۱} \sim \dots \sim v_{k}, v_{k} = v_{۰}$ بخوان: v صفر مجاور v یک است و همین‌طور تا v k؛ اگر v k دوباره v صفر باشد، دور استیعنی: مسیر از روی یال‌ها از یک رأس به رأس دیگر می‌رود؛ اگر به جای شروع برگردد، دور می‌شود.
$∣ E ∣ = ∣ V ∣ - ۱$ بخوان: تعداد یال‌ها برابر است با تعداد رأس‌ها منهای یکیعنی: گراف همبند با این شمار، درخت است: به‌هم‌پیوسته و بی‌دور.
$A_{uv} = ۱ \Leftrightarrow u \sim v$ بخوان: A از u و v یک است اگر و تنها اگر u با v مجاور باشدیعنی: ماتریس مجاورت A هر جا یال هست یک دارد و هر جا نیست صفر.
$(A^{۲})_{ij} = \sum_{k} A_{ik} A_{k j}$ بخوان: A به توان دو، درایهٔ i و j، برابر است با مجموع روی k از A از i و k ضرب در A از k و jیعنی: این درایه تعداد گشت‌های به طول دو از i تا j را می‌شمارد: برای هر رأس میانی k یکی.
$\sum_{v \in V} de g v = ۲ ∣ E ∣$ بخوان: مجموع درجهٔ v روی همهٔ v در V برابر است با دو برابر تعداد یال‌هایعنی: هر یال دو سر دارد، پس جمع همهٔ درجه‌ها هر یال را دو بار می‌شمارد.

داستان: پل‌ها و راه‌های یک پارک

زیرنویس:

روی هر سطر بزن تا کلمه‌هایش را ببینی.

$G = (V, E)$ یک پارک چند نقطه و راه‌هایی میان آن‌ها دارد. برای هر نقطه یک نقطه و برای هر راه یک خط بکش: یک گراف.
$∣ V ∣ = ۵, ∣ E ∣ = ۵$ پارک پنج نقطه دارد، با نام‌های a تا e، و پنج راه.
$b \sim c, b \sim d, a ≁ d$ نقطهٔ b کنار c و d است؛ نقطهٔ a کنار d نیست.
$de g b = ۳, de g a = ۱$ سه راه به b می‌رسند؛ فقط یکی به a.
$a \sim b \sim d \sim e$ گشتی از a تا e که هیچ نقطه‌ای را دوباره نمی‌رود: مسیری با سه گام.
$b \sim c \sim d \sim b$ از b به c، به d و دوباره به b: یک دور، رفت و برگشت.
$v \in V \sum de g v = ۱ + ۳ + ۲ + ۳ + ۱ = ۱۰ = ۲ \cdot ۵$ راه‌های رسیده به هر نقطه را جمع کن: ده، یعنی دو برابر پنج راه، چون هر راه دو سر دارد.
$A_{b c} = ۱, A_{a d} = ۰$ در جدول صفر و یک، درایهٔ b و c برابر ۱ است؛ برای a و d برابر ۰.
$(A^{۲})_{a d} = ۱$ ضرب جدول در خودش یک گشت دوگامی از a تا d نشان می‌دهد: از طریق b.
$∣ E ∣ = ۴ = ∣ V ∣ - ۱$ شورا راه میان c و d را می‌بندد. حالا پارک یک راه کمتر از نقطه‌ها دارد: یک درخت.

این داستان با کلمه‌ها ۶۴۲ حرف است؛ با نمادها ۱۰۴.

بخوانش

چه می‌گوید؟

$u \sim v$

$de g v = ۰$

$∣ E ∣ = ∣ V ∣ - ۱$

$(A^{۲})_{ij} = ۳$

$∣ V ∣ = ۶, ∣ E ∣ = ۹$

$de g v = ∣ V ∣ - ۱$

$a ≁ b$

$A_{v v} = ۰$

$v \in V \sum de g v = ۱۴$

$v_{۰} \sim v_{۱} \sim v_{۲} \sim v_{۳}$

$(A^{۲})_{ii} = de g i$

$∣ E ∣ = ∣ V ∣$

بنویسش

کدام نمادنویسی همین را می‌گوید؟

درجهٔ رأس v برابر چهار است.

جمع همهٔ درجه‌ها دو برابر تعداد یال‌ها می‌شود.

تعداد گشت‌های به طول دو از i تا j برابر درایهٔ سطر i و ستون j از ماتریس A به توان دو است.

رأس‌های a و b مجاور نیستند.

گشتی با دو گام: از a به b، بعد از b به c.

دوری به طول سه: از a به b، به c و دوباره به a.

گراف هفت رأس و شش یال دارد.

گرافی با ده یال: جمع درجه‌هایش بیست است.

رأس v منزوی است: هیچ یالی به آن نمی‌رسد.

در ماتریس مجاورت: میان u و v یالی نیست.

تعداد گشت‌های به طول سه از i تا j.

درختی با n رأس، n منهای یک یال دارد.

بسازش

کاشی‌ها را به ترتیب بزن. یکی از کاشی‌ها اضافه است.

تعداد یال‌ها برابر است با تعداد رأس‌ها منهای یک.

درایهٔ A در u و v برابر یک است اگر و تنها اگر u و v مجاور باشند.

تعداد گشت‌های دوگامی از i تا j: مجموع روی k از A از i و k ضرب در A از k و j.

دوری از چهار رأس: از a به b، به c، به d و دوباره به a.

درجهٔ v برابر جمع سطر v از ماتریس مجاورت است.

در درخت، جمع درجه‌ها دو برابر تعداد یال‌هاست، و تعداد یال‌ها تعداد رأس‌ها منهای یک است.

چالش‌ها

معماهای خلاقانه‌ای که همهٔ نمادهای این فصل را به کار می‌برند. عجله نکن؛ ساعتی در کار نیست.

1 پارک به شکل جدول

این جدول ماتریس مجاورتِ پارکِ داستان است. هر جمله دربارهٔ پارک را داوری کن.

	$a$	$b$	$c$	$d$	$e$
$a$		✓
$b$	✓		✓	✓
$c$		✓		✓
$d$		✓	✓		✓
$e$				✓

تیک یعنی نقطهٔ سطر با نقطهٔ ستون مجاور است.

$de g b = ۳$
$\forall v : de g v \geq ۱$
$\exists v : de g v = ۰$
$a \sim e$
$\exists u \exists v : u \sim v \land de g u = de g v = ۳$
$\exists v \forall u \neq = v : u \sim v$

2 واژه‌های گراف

پنج خط دربارهٔ یک گراف. هر کدام را به معنایش وصل کن.

روی یک سطر بزن، بعد روی معنایش.

3 شمار یال‌های درخت

درختی روی نقطه‌های پارک باید یک راه کمتر از نقطه‌ها داشته باشد. یکی از کاشی‌ها غلط است. پیدایش کن و درستش کن.

روی کاشیِ غلط بزن.

4 هر راه دو سر دارد

این باید بگوید جمع درجه‌ها دو برابر تعداد یال‌هاست. یکی از کاشی‌ها غلط است. پیدایش کن و درستش کن.

روی کاشیِ غلط بزن.

5 گشت‌های دوگامی

ماتریس مربوط به دور چهارتایی است: چهار نقطه در یک حلقه، هر کدام کنار دو همسایه‌اش. از رأس ۱ تا رأس ۳ چند گشت دوگامی هست؟

$A = ۰ ۱ ۰ ۱ ۱ ۰ ۱ ۰ ۰ ۱ ۰ ۱ ۱ ۰ ۱ ۰, (A^{۲})_{۱۳} = ?$

6 درجه‌های ناممکن

پنج نقطه درجه‌های ۳ و ۳ و ۲ و ۲ و یک درجهٔ دیگر، x، دارند. کدام مقدار x ناممکن است؟

$de g = (۳, ۳, ۲, ۲, x)$

7 پارکی شلوغ اما نه خیلی

هر نقطه دست‌کم به یک راه می‌رسد، اما هیچ نقطه‌ای به همهٔ نقطه‌های دیگر نمی‌رسد. آن را با نماد بنویس.

نوشتهٔ تو

8 دوستی مشترک

هر دو نقطهٔ متفاوت، نقطه‌ای دارند که با هر دو مجاور است. آن را با نماد بنویس.

نوشتهٔ تو

9 کانون

پنج اتاق یک خانه و درهای میانشان، به شکل ماتریس مجاورت. هر جمله دربارهٔ این گراف را داوری کن.

	$p$	$q$	$r$	$s$	$t$
$p$		✓	✓	✓	✓
$q$	✓		✓
$r$	✓	✓
$s$	✓
$t$	✓

تیک یعنی اتاقِ سطر به اتاقِ ستون در دارد.

$\exists v \forall u \neq = v : u \sim v$
$\sum_{v \in V} de g v = ۱۰$
$∣ E ∣ = ∣ V ∣ - ۱$
$q \sim r \sim p \sim q$
$s \sim t$
$(A^{۲})_{s t} = ۱$

10 شش ایستگاه، پنج خط

شش ایستگاه یک راه‌آهن کوچک و خط‌های میانشان، به شکل ماتریس مجاورت. هر جمله دربارهٔ این گراف را داوری کن.

	$a$	$b$	$c$	$d$	$e$	$f$
$a$		✓
$b$	✓		✓
$c$		✓		✓	✓
$d$			✓
$e$			✓			✓
$f$					✓

تیک یعنی خطی ایستگاهِ سطر را به ایستگاهِ ستون وصل می‌کند.

$∣ E ∣ = ∣ V ∣ - ۱$
$\exists v : de g v = ۳$
$\forall v : de g v \leq ۲$
$a \sim b \sim c \sim e \sim f$
$\exists u, v, w : u \sim v \sim w \sim u$
$\sum_{v \in V} de g v = ۱۲$

11 خواندن جدول

پنج چیز که می‌شود از ماتریس مجاورت خواند. هر کدام را به معنایش وصل کن.

روی یک سطر بزن، بعد روی معنایش.

12 پنج شمار

پنج شمار دربارهٔ یک گراف. هر کدام را به چیزی که می‌شمارد وصل کن.

روی یک سطر بزن، بعد روی معنایش.

13 از میانه

این باید گشت‌های دوگامی از i تا j را بشمارد: یک گام از i به یک k، بعد یک گام از k به j. یکی از کاشی‌ها غلط است. پیدایش کن و درستش کن.

روی کاشیِ غلط بزن.

14 حلقه را ببند

این باید دوری از a و b و c باشد: سه گام که به آغاز برمی‌گردد. یکی از کاشی‌ها غلط است. پیدایش کن و درستش کن.

روی کاشیِ غلط بزن.

15 شش نقطه، هر یک با دو راه

شش نقطه در یک پارک، هر کدام با دقیقاً دو راه. چند راه هست؟

$de g = (۲, ۲, ۲, ۲, ۲, ۲), ∣ E ∣ = ?$

16 درختی با ده رأس

یک درخت ده رأس دارد. جمع درجه‌هایش چند است؟

$∣ V ∣ = ۱۰, ∣ E ∣ = ∣ V ∣ - ۱, v \in V \sum de g v = ?$

17 رفت و برگشت

چهار نقطه، هر جفت با یک راه وصل. چند گشت دوگامی از نقطهٔ ۱ شروع می‌شود و به نقطهٔ ۱ برمی‌گردد؟

$A = ۰ ۱ ۱ ۱ ۱ ۰ ۱ ۱ ۱ ۱ ۰ ۱ ۱ ۱ ۱ ۰, (A^{۲})_{۱۱} = ?$

18 از هر جا سه راه

در این پارک هر نقطه دقیقاً سه راه دارد. آن را با نماد بنویس، بعد مقایسه کن.

نوشتهٔ تو

19 جایی یک مثلث

جایی در گراف سه رأس هستند که هر کدام با دو تای دیگر مجاور است. آن را با نماد بنویس، بعد مقایسه کن.

نوشتهٔ تو

داستان خودت را بگو

گراف کوچکی از خودت بکش (نقشهٔ راه، یک خانواده، یک صفحهٔ بازی) و رأس‌ها و یال‌هایش و درجهٔ یکی از رأس‌ها را بنویس.

فقط روی همین دستگاه نگه داشته می‌شود.

گراف: نقطه‌ها، خط‌ها و شمردن گام‌ها

الفبا

داستان: پل‌ها و راه‌های یک پارک

بخوانش

بنویسش

بسازش

چالش‌ها

1 پارک به شکل جدول

2 واژه‌های گراف

3 شمار یال‌های درخت

4 هر راه دو سر دارد

5 گشت‌های دوگامی

6 درجه‌های ناممکن

7 پارکی شلوغ اما نه خیلی

8 دوستی مشترک

9 کانون

10 شش ایستگاه، پنج خط

11 خواندن جدول

12 پنج شمار

13 از میانه

14 حلقه را ببند

15 شش نقطه، هر یک با دو راه

16 درختی با ده رأس

17 رفت و برگشت

18 از هر جا سه راه

19 جایی یک مثلث

داستان خودت را بگو

دانلود برای استفاده بدون اینترنت