Lesson notes & every answer, in textสรุปบทเรียนและเฉลยทุกข้อ แบบข้อความ
Introduction to Networksเครือข่ายเบื้องต้น
Year 10 · NSW Stage 5 · free step-by-step lesson, every question with its answer and the reason behind itบทเรียนฟรีทีละขั้น ทุกข้อมีเฉลยและเหตุผลกำกับ
1. Wordsคำศัพท์
What is a network?เครือข่าย (network) คืออะไร
Add up all the degreesบวกดีกรีของทุกจุด
- $S=2+3+4+3+2$$S$ is the sum of the degrees of A, B, C, D and E.$S$ คือผลรวมดีกรีของ A, B, C, D และ E
- $=14$
- $2\times7=14$G has $7$ edges. Two times $7$ is also $14$.G มีเส้นเชื่อม $7$ เส้น · $2$ คูณ $7$ ก็ได้ $14$ เหมือนกัน
Sum of degrees = 2 × number of edges.ผลรวมดีกรี = 2 × จำนวนเส้นเชื่อม
- How many edges does network G have?เครือข่าย G มีเส้นเชื่อมกี่เส้น?
Answer:เฉลย: $7$Name every edge: $AB,\ AC,\ BC,\ BD,\ CD,\ CE,\ DE$ Seven pairs of letters, so $7$ edges.เรียกชื่อทุกเส้น: $AB,\ AC,\ BC,\ BD,\ CD,\ CE,\ DE$ ได้ตัวอักษร $7$ คู่ จึงมี $7$ เส้น
- The degree of a vertex is the number of edges that touch it. Press Play to count it for C. Now find the degree of B.ดีกรี (degree) ของจุดยอด คือจำนวนเส้นเชื่อมที่แตะจุดนั้น · กดเล่นเพื่อดูการนับที่ C · แล้วหาดีกรีของ B
Answer:เฉลย: $3$Edges at B: $BA,\ BC,\ BD$เส้นที่แตะ B: $BA,\ BC,\ BD$
2. Isomorphic graphsกราฟไอโซมอร์ฟิก
Same joins, different drawing.เส้นเชื่อมชุดเดียวกัน แต่วาดต่างกัน
Same network, different drawingเครือข่ายเดียวกัน วาดต่างกัน
- Which vertex of H matches C in G?จุดยอดไหนของ H คู่กับ C ของ G?
Answer:เฉลย: $W$Match the degree 4s: $C\leftrightarrow W$ C and W are the only vertices of degree $4$.จับคู่ดีกรี 4: $C\leftrightarrow W$ C กับ W เป็นจุดยอดดีกรี $4$ เพียงจุดเดียวของแต่ละกราฟ
- Press Play. Each vertex of G slides to its partner in H. Does any edge appear or disappear?กดเล่น · จุดยอดแต่ละจุดของ G เลื่อนไปที่คู่ของมันใน H · มีเส้นเชื่อมเพิ่มขึ้นหรือหายไปไหม?
Answer:เฉลย: Noไม่มีMoving keeps the joins: $AB\to UV,\ \ AC\to UW,\ \ CE\to WY$ The edges stretch, but each join stays. That is what isomorphic means.ขยับจุดแล้ว เส้นยังต่อเหมือนเดิม: $AB\to UV,\ \ AC\to UW,\ \ CE\to WY$ เส้นยืดได้ แต่การต่อไม่เปลี่ยน · นี่คือความหมายของไอโซมอร์ฟิก
- M and N both have $5$ vertices and $5$ edges. Are they isomorphic?M และ N มีจุดยอด $5$ จุด และเส้นเชื่อม $5$ เส้นเท่ากัน · สองกราฟนี้ไอโซมอร์ฟิกกันไหม?
Answer:เฉลย: Noไม่ใช่Degree lists differ: $M:\ 2,\ 2,\ 2,\ 2,\ 2$ $N:\ 1,\ 2,\ 2,\ 2,\ 3$ Careful: the same degree list still does not prove isomorphic. You must match the edges.รายการดีกรีไม่ตรงกัน: $M:\ 2,\ 2,\ 2,\ 2,\ 2$ $N:\ 1,\ 2,\ 2,\ 2,\ 3$ ระวัง: รายการดีกรีตรงกันก็ยังไม่พอ · ต้องจับคู่เส้นเชื่อมด้วย
3. Planar graphsกราฟเชิงระนาบ
Planar = it CAN be drawn with no crossings.เชิงระนาบ = วาดได้โดยไม่มีเส้นตัดกัน
What does planar mean?เชิงระนาบ (planar) แปลว่าอะไร
- To decide if a graph is planar, what matters?จะบอกว่ากราฟเป็นกราฟเชิงระนาบไหม ต้องดูอะไร?
Answer:เฉลย: Whether it can be drawn with no crossingsวาดได้โดยไม่มีเส้นตัดกันหรือเปล่าOne good drawing is enough: $K:\ \ 1\to0$ You only need to find one drawing with no crossings.มีรูปดีรูปเดียวก็พอ: $K:\ \ 1\to0$ ขอแค่หารูปที่ไม่มีเส้นตัดกันได้หนึ่งรูป
- In drawing 1 the two diagonals cross. There is no vertex where they cross, like a bridge over a road. How many vertices does K have?ในรูปที่ 1 เส้นทแยงสองเส้นตัดกัน · ตรงจุดตัดไม่มีจุดยอด เหมือนสะพานข้ามถนน · K มีจุดยอดกี่จุด?
Answer:เฉลย: $4$A crossing is not a vertex: $P,\ Q,\ R,\ S$จุดตัดไม่ใช่จุดยอด: $P,\ Q,\ R,\ S$
- Press Play. Only P moves, into the triangle. After P moves, how many edges does K have?กดเล่น · มีแค่ P ที่ขยับเข้าไปในสามเหลี่ยม · หลัง P ขยับ K มีเส้นเชื่อมกี่เส้น?
Answer:เฉลย: $6$Moving keeps every edge: $PQ,\ QR,\ RS,\ SP,\ PR,\ QS$ Moving vertices is allowed. Removing or adding an edge is not.ขยับแล้วเส้นยังครบ: $PQ,\ QR,\ RS,\ SP,\ PR,\ QS$ ขยับจุดยอดได้ · แต่ลบหรือเพิ่มเส้นเชื่อมไม่ได้
- Here edge QS goes round the outside, not through the middle. Is this still a drawing of K?รูปนี้เส้น QS อ้อมไปด้านนอก ไม่ผ่านตรงกลาง · ยังเป็นรูปของ K อยู่ไหม?
Answer:เฉลย: Yesใช่Bending removes a crossing: $PQ,\ QR,\ RS,\ SP,\ PR,\ QS$ Same $6$ joins. Bending an edge is a second way to remove a crossing.ดัดเส้นก็ลบจุดตัดได้: $PQ,\ QR,\ RS,\ SP,\ PR,\ QS$ เส้นเชื่อม $6$ เส้นเดิม · การดัดเส้นเป็นอีกวิธีที่ลบจุดตัดได้
- Your turn. Drag the vertices until the crossings reach $0$. Stuck? Press Show me. Is this graph planar?ลองเอง · ลากจุดยอดจนจุดตัดเหลือ $0$ · ถ้าติด กดดูเฉลย · กราฟนี้เป็นกราฟเชิงระนาบไหม?
Answer:เฉลย: Yesใช่0 crossings proves planar: $7\to0$จุดตัด 0 พิสูจน์ว่าเป็นเชิงระนาบ: $7\to0$
4. Facesหน้า (face)
Count the regions, and the outside.นับบริเวณ และนับด้านนอกด้วย
Not every graph is planarไม่ใช่ทุกกราฟจะเป็นกราฟเชิงระนาบ
A face is a region the edges cut out. Count the faces of G.หน้า (face) คือบริเวณที่เส้นเชื่อมแบ่งไว้ · นับหน้าของ G
- $1$Face 1: the triangle ABC.หน้าที่ 1: สามเหลี่ยม ABC
- $1+1=2$Face 2: the triangle BDC.หน้าที่ 2: สามเหลี่ยม BDC
- $2+1=3$Face 3: the triangle CDE.หน้าที่ 3: สามเหลี่ยม CDE
- $3+1=4$The region outside the network is a face too.บริเวณด้านนอกเครือข่ายก็นับเป็นหน้าด้วย
G has $4$ faces: $3$ inside and $1$ outside.G มี $4$ หน้า: ข้างใน $3$ และด้านนอก $1$
- A graph is drawn with $3$ crossings. Does that prove it is not planar?กราฟหนึ่งวาดออกมามีจุดตัด $3$ จุด · แบบนี้พิสูจน์ได้ไหมว่าไม่ใช่กราฟเชิงระนาบ?
Answer:เฉลย: Noไม่ได้One drawing proves nothing: $K:\ \ 1\to0$ $K_5:\ \ 5\to1$รูปเดียวพิสูจน์ไม่ได้: $K:\ \ 1\to0$ $K_5:\ \ 5\to1$
- Use the redrawn K, with P inside the triangle. How many faces does it have?ใช้ K ที่วาดใหม่ ซึ่ง P อยู่ในสามเหลี่ยม · มีกี่หน้า?
Answer:เฉลย: $4$3 inside + 1 outside: $3+1=4$ข้างใน 3 + ด้านนอก 1: $3+1=4$
5. Euler's formulaสูตรของออยเลอร์
$v+f=e+2$ for every connected planar graph.$v+f=e+2$ ใช้ได้กับกราฟเชิงระนาบที่เชื่อมต่อกันทุกกราฟ
Euler's formula: $v+f=e+2$สูตรของออยเลอร์: $v+f=e+2$
This works for every connected planar graph.ใช้ได้กับกราฟเชิงระนาบที่เชื่อมต่อกันทุกกราฟ
Check $v+f=e+2$ for Gตรวจ $v+f=e+2$ กับ G
- $v+f=5+4$Put in $v=5$ and $f=4$.แทน $v=5$ และ $f=4$
- $=9$
- $e+2=7+2$Put in $e=7$.แทน $e=7$
- $=9$Both sides are $9$.ทั้งสองข้างได้ $9$
A connected planar graph has $6$ vertices and $9$ edges. Find the number of faces.กราฟเชิงระนาบที่เชื่อมต่อกันมีจุดยอด $6$ จุด และเส้นเชื่อม $9$ เส้น · หาจำนวนหน้า
- $v+f=e+2$Write the formula first.เขียนสูตรก่อน
- $6+f=9+2$Put the numbers in.แทนตัวเลข
- $6+f=11$Take $6$ from both sides.ลบ $6$ ทั้งสองข้าง
- $f=5$The graph has $5$ faces.กราฟนี้มี $5$ หน้า
A connected planar graph has $12$ edges and $6$ faces. Find $v$.กราฟเชิงระนาบที่เชื่อมต่อกันมีเส้นเชื่อม $12$ เส้น และ $6$ หน้า · หา $v$
- $v+f=e+2$Write the formula first.เขียนสูตรก่อน
- $v+6=12+2$Put the numbers in.แทนตัวเลข
- $v+6=14$Take $6$ from both sides.ลบ $6$ ทั้งสองข้าง
- $v=8$A cube is a graph like this: $8$ corners, $12$ edges, $6$ faces.ลูกบาศก์เป็นกราฟแบบนี้: มุม $8$ มุม ขอบ $12$ เส้น หน้า $6$ หน้า
- Check it for K: $v=4$, $e=6$, $f=4$. What is $v+f$?ตรวจกับ K: $v=4$, $e=6$, $f=4$ · $v+f$ ได้เท่าไร?
Answer:เฉลย: $8$Both sides match: $v+f=4+4$ $=8$ $e+2=6+2$ $=8$สองข้างเท่ากัน: $v+f=4+4$ $=8$ $e+2=6+2$ $=8$
- A connected planar graph has $7$ vertices and $10$ edges. How many faces does it have?กราฟเชิงระนาบที่เชื่อมต่อกันมีจุดยอด $7$ จุด และเส้นเชื่อม $10$ เส้น · มีกี่หน้า?
Answer:เฉลย: $5$Formula, then numbers: $v+f=e+2$ $7+f=10+2$ $7+f=12$ $f=5$สูตรก่อน แล้วแทนค่า: $v+f=e+2$ $7+f=10+2$ $7+f=12$ $f=5$
- A connected planar graph has $8$ vertices and $5$ faces. How many edges does it have?กราฟเชิงระนาบที่เชื่อมต่อกันมีจุดยอด $8$ จุด และ $5$ หน้า · มีเส้นเชื่อมกี่เส้น?
Answer:เฉลย: $11$Formula, then numbers: $v+f=e+2$ $8+5=e+2$ $13=e+2$ $11=e$สูตรก่อน แล้วแทนค่า: $v+f=e+2$ $8+5=e+2$ $13=e+2$ $11=e$
6. Eulerian trailsรอยเดินออยเลอร์
Count the odd vertices: 0, 2, or more.นับจุดยอดดีกรีคี่: 0, 2 หรือมากกว่า
Trail and circuitรอยเดิน (trail) และวงจร (circuit)
- Trace the bow tie. Tap the edges one after another, each one starting where the last one ended. Use every edge once. Did you finish where you started?ลากรูปโบว์ · แตะเส้นเชื่อมทีละเส้น แต่ละเส้นต้องเริ่มตรงที่เส้นก่อนจบ · ใช้ทุกเส้นครั้งเดียว · จบที่จุดเริ่มต้นไหม?
Answer:เฉลย: Yes: an Eulerian circuitใช่: เป็นวงจรออยเลอร์Back at the start: $M\to X\to Y\to M\to Z\to W\to M$กลับมาที่จุดเริ่ม: $M\to X\to Y\to M\to Z\to W\to M$
- In G, B and D are odd (degree $3$). Start at B and use every edge once. Where do you finish?ใน G จุด B กับ D มีดีกรีคี่ (ดีกรี $3$) · เริ่มที่ B แล้วใช้ทุกเส้นครั้งเดียว · จบที่จุดไหน?
Answer:เฉลย: At Dที่ DOdd to odd: $B:\ 3,\quad D:\ 3$ A trail with $2$ odd vertices starts at one and finishes at the other.คี่ไปคี่: $B:\ 3,\quad D:\ 3$ รอยเดินที่มีจุดคี่ $2$ จุด เริ่มที่จุดหนึ่ง และจบที่อีกจุด
- The bow tie has degrees $2, 2, 4, 2, 2$. How many of its vertices have an odd degree?รูปโบว์มีดีกรี $2, 2, 4, 2, 2$ · มีจุดยอดดีกรีคี่กี่จุด?
Answer:เฉลย: $0$All even: $2,\ 2,\ 4,\ 2,\ 2$ $0$ odd vertices, so there is an Eulerian circuit. That is the one you traced.คู่ทั้งหมด: $2,\ 2,\ 4,\ 2,\ 2$ จุดคี่ $0$ จุด จึงมีวงจรออยเลอร์ · คือวงที่ลากไปเมื่อกี้
- Every vertex of K has degree $3$. Does K have an Eulerian circuit, an Eulerian trail, or neither?จุดยอดทุกจุดของ K มีดีกรี $3$ · K มีวงจรออยเลอร์ รอยเดินออยเลอร์ หรือไม่มีทั้งสองแบบ?
Answer:เฉลย: Neitherไม่มีทั้งสองแบบ4 odd, so neither: $3,\ 3,\ 3,\ 3$คี่ 4 จุด จึงไม่มี: $3,\ 3,\ 3,\ 3$
- In 1736 Königsberg had $7$ bridges. Euler drew the land as vertices and the bridges as edges. Can you cross every bridge once, and no bridge twice?ปี 1736 เมืองเคอนิกส์แบร์กมีสะพาน $7$ แห่ง · ออยเลอร์วาดแผ่นดินเป็นจุดยอด และสะพานเป็นเส้นเชื่อม · เดินข้ามทุกสะพาน โดยไม่ข้ามสะพานไหนซ้ำ ได้ไหม?
Answer:เฉลย: Noไม่ได้4 odd vertices: $I:\ 5,\quad N:\ 3,\quad S:\ 3,\quad T:\ 3$ Two pairs of bridges join the same land, so this graph has multiple edges.จุดคี่ 4 จุด: $I:\ 5,\quad N:\ 3,\quad S:\ 3,\quad T:\ 3$ มีสะพานสองคู่ที่ต่อแผ่นดินเดียวกัน กราฟนี้จึงมีเส้นเชื่อมซ้ำ (multiple edges)
7. Exam formรูปแบบข้อสอบ
Short exam questions, all five ideas.ข้อสอบสั้น ครบทั้งห้าเรื่อง
The five factsห้าเรื่องที่ต้องจำ
- A network has $10$ edges. What is the sum of the degrees of its vertices?เครือข่ายหนึ่งมีเส้นเชื่อม $10$ เส้น · ผลรวมดีกรีของจุดยอดทั้งหมดเท่ากับเท่าไร?
Answer:เฉลย: $20$1 mark: $\text{A1}\quad 2\times10=20$1 คะแนน: $\text{A1}\quad 2\times10=20$
- The sum of the degrees of a network is $18$. How many edges does it have?ผลรวมดีกรีของเครือข่ายหนึ่งเท่ากับ $18$ · เครือข่ายนี้มีเส้นเชื่อมกี่เส้น?
Answer:เฉลย: $9$2 marks: $\text{M1}\quad 2e=18$ $\text{A1}\quad e=9$ Write the rule $2e=18$ first. It earns the method mark.2 คะแนน: $\text{M1}\quad 2e=18$ $\text{A1}\quad e=9$ เขียน $2e=18$ ก่อน · ได้คะแนนวิธีทำ
- A connected network has vertices of degree $2, 4, 4, 3$ and $3$. Does it have an Eulerian circuit, an Eulerian trail, or neither?เครือข่ายที่เชื่อมต่อกันมีจุดยอดดีกรี $2, 4, 4, 3$ และ $3$ · มีวงจรออยเลอร์ รอยเดินออยเลอร์ หรือไม่มีทั้งสองแบบ?
Answer:เฉลย: An Eulerian trailรอยเดินออยเลอร์2 marks: $\text{M1}\quad 3,\ 3$ $\text{A1}\quad 2\to\text{trail}$ Name the $2$ odd vertices. The reason earns the first mark.2 คะแนน: $\text{M1}\quad 3,\ 3$ $\text{A1}\quad 2\to\text{trail}$ บอกว่ามีจุดคี่ $2$ จุด · เหตุผลคือคะแนนแรก
- Graph P has degree list $1, 2, 2, 3$. Graph Q has degree list $2, 2, 2, 2$. Can P and Q be isomorphic?กราฟ P มีรายการดีกรี $1, 2, 2, 3$ · กราฟ Q มีรายการดีกรี $2, 2, 2, 2$ · P กับ Q ไอโซมอร์ฟิกกันได้ไหม?
Answer:เฉลย: Noไม่ได้1 mark: $\text{A1}\quad 1,2,2,3\ne2,2,2,2$1 คะแนน: $\text{A1}\quad 1,2,2,3\ne2,2,2,2$
8. Exercise setชุดโจทย์
Each question changes one thing from the one before it.แต่ละข้อเปลี่ยนจากข้อก่อนหน้าแค่อย่างเดียว
- A network has degrees $1, 2, 3, 3, 3$. How many edges does it have?เครือข่ายหนึ่งมีดีกรี $1, 2, 3, 3, 3$ · มีเส้นเชื่อมกี่เส้น?
Answer:เฉลย: $6$Sum of degrees $12$, then halve it.ผลรวมดีกรีได้ $12$ แล้วหารสอง
- A connected planar graph has $15$ vertices and $23$ edges. How many faces does it have?กราฟเชิงระนาบที่เชื่อมต่อกันมีจุดยอด $15$ จุด และเส้นเชื่อม $23$ เส้น · มีกี่หน้า?
Answer:เฉลย: $10$Same formula, bigger numbers: $15+f=25$.สูตรเดิม ตัวเลขใหญ่ขึ้น: $15+f=25$
- A cube has $8$ corners and $12$ edges. Drawn as a planar graph, how many faces does it have?ลูกบาศก์มีมุม $8$ มุม และขอบ $12$ เส้น · ถ้าวาดเป็นกราฟเชิงระนาบ จะมีกี่หน้า?
Answer:เฉลย: $6$A solid is a planar graph. Corners are vertices: $8+f=14$.ทรงตันเป็นกราฟเชิงระนาบ · มุมคือจุดยอด: $8+f=14$
- A network has $6$ vertices, each of degree $3$. How many edges does it have?เครือข่ายมีจุดยอด $6$ จุด แต่ละจุดมีดีกรี $3$ · มีเส้นเชื่อมกี่เส้น?
Answer:เฉลย: $9$Multiply first: $6\times3=18$. Then $18\div2$.คูณก่อน: $6\times3=18$ · แล้ว $18\div2$
- A connected planar graph has $9$ edges and $5$ faces. How many vertices does it have?กราฟเชิงระนาบที่เชื่อมต่อกันมีเส้นเชื่อม $9$ เส้น และ $5$ หน้า · มีจุดยอดกี่จุด?
Answer:เฉลย: $6$Solve for $v$ instead of $f$: $v+5=11$.แก้หา $v$ แทน $f$: $v+5=11$
- A connected network has exactly $4$ vertices of odd degree. What is the least number of edges you must add so that it has an Eulerian trail?เครือข่ายที่เชื่อมต่อกันมีจุดยอดดีกรีคี่ $4$ จุดพอดี · ต้องเพิ่มเส้นเชื่อมอย่างน้อยกี่เส้น จึงจะมีรอยเดินออยเลอร์?
Answer:เฉลย: $1$One new edge between two odd vertices makes both even: $4\to2$ odd.เพิ่มหนึ่งเส้นระหว่างจุดคี่สองจุด ทั้งคู่กลายเป็นคู่: คี่ $4\to2$
All free lessonsบทเรียนฟรีทั้งหมด · Free maths libraryคลังเรียนฟรี