A vertex頂点 is a point in a graph that stands for an object or location, such as a person, a station, or a computer.
A graphグラフ is a diagram that shows how things are connected, using a set of vertices and lines (edges) that join them. A vertex is the "what" in "what is connected to what," and it is drawn as a circle or a dot. Which things become vertices depends on what you want to show: in the same railway network, you can treat stations as vertices, or you can treat railway lines (routes) as vertices.
AnalogyThink of the pins you drop on a map to mark meeting spots. A pin only marks a place; how to get from one pin to another is the job of a separate line.
How to rememberIt is the same word as the vertex of a triangle, the corner point where two sides meet.
Exam points
ExamFor route problems, treat the start, each stopover, and the destination as vertices頂点, and the roads between them as edges 辺; this makes the problem easier to work through.
Mix-upA vertex頂点 is the object itself, while an edge 辺 is the relationship between objects. Tell them apart by asking whether it is a point or a line.
A nodeノード is the English-derived name for a vertex of a graph, and it refers to exactly the same thing.
In IT, devices connected to a network and the elements of data structures such as trees and lists are also called nodes. All of them are elements placed at the ends of connections, so they play the same role as the vertices of a graph.
How to rememberThe English word node originally means a knot. Picture the knots where the threads of a net cross.
Exam points
Mix-upA nodeノード and a vertex 頂点 differ only in name; they are not separate components.
An edge辺 is a line that joins two vertices and shows that a connection or relationship exists between them.
An edge always has a vertex at each end, and which two vertices it joins determines the relationship. An edge can carry a value such as distance, time, or cost, and this value is called a weight. With weighted edges, you can compare routes from one place to another by adding up the values on the edges.
AnalogyThink of the roads between towns. A road connects two towns, and if you write the travel time on each road, you can tell whether a route is a detour.
How to rememberThe kanji 辺 is the one used for a side of a triangle; remember it as the line joining one corner (vertex) to another.
Exam points
ExamIn a graph where each edge辺 carries its travel time as a weight 重み, the travel time of a route is the sum of the weights of the edges it passes through.
ExamIf every pair of vertices 頂点 is joined by exactly one edge辺, a graph with n vertices has n(n−1)/2 edges. For example, 5 vertices give 10 edges.
The loanword edgeエッジ is the English-derived name for a graph's edge辺, and it refers to exactly the same thing.
Where vertices are called nodes (ノード), the term 辺 is usually replaced by the loanword edge (エッジ) as well, and a graph is described as a set of nodes and edges. In networking, the lines or links that connect devices (nodes) are sometimes treated as edges. The edge in edge computing (エッジコンピューティング) is a different sense: the outer end of a network, close to the users and devices.
How to rememberThe English word edge means a rim or border. Link it to the border of a shape, that is, the line running from corner to corner.
Exam points
ExamWhen you draw an ordering relation as a diagram, each related pair becomes one edgeエッジ, so the number of edges you draw equals the number of pairs.
Mix-upThe loanword edgeエッジ and the native term edge 辺 differ only in name; they are not separate components.
A directed graph有向グラフ is a graph whose edges have a direction and are drawn as arrows.
← Scroll the figure sideways →
An arrow shows a relationship running from the vertex at its tail to the vertex at its head, and the reverse relationship does not hold unless there is a separate arrow for it. Directed graphs represent things like the order of tasks, links between web pages, and road networks made of one-way streets.
AnalogyThink of a road network with one-way signs. You can only go the way the signs point, and getting back takes a different road.
How to rememberDirected literally means having a direction. Check whether the line ends in an arrowhead.
Exam points
ExamAn ordered pair (P, Q) is drawn as one arrow with its tail at P and its head at Q. Swapping the tail and the head gives a different relationship.
An undirected graph無向グラフ is a graph whose edges have no direction and are drawn as lines without arrowheads.
← Scroll the figure sideways →
The two vertices joined by an edge are equal partners, and the relationship is the same from either side. Undirected graphs represent things like people who know each other and road networks you can travel in both directions.
AnalogyThink of a handshake. If A is shaking hands with B, then B is shaking hands with A.
How to rememberUndirected is directed with un- in front. The un- tells you there is no arrowhead.
Exam points
Mix-upOne edge of an undirected graph無向グラフ corresponds to two arrows pointing in opposite directions in a directed graph 有向グラフ.
Directed Graph vs. Undirected Graph
Aspect
Directed Graph
Undirected Graph
Key differenceEdge direction
Present (drawn as arrows)
Absent (drawn as lines)
Nature of the relationship
One way, from tail to head
Both end vertices are equal
Examples
Order of tasks, links between web pages
People who know each other
Key points
A graph is made of vertices, drawn as points, and edges, the lines that join them.
In Japanese, nodeノード is the loanword for vertex 頂点 and edgeエッジ the loanword for edge 辺; each pair refers to the same thing.
Each ordered pair is drawn as one arrow, and swapping its tail and head gives a different relationship.
Giving edges a weight such as travel time lets you compare route lengths by summing the weights of the edges passed through.
When every pair of vertices is joined by an edge, n vertices give n(n−1)/2 edges.