MYP Extended Mathematics Graph Theory and Vectors Key Definitions

A **bipartite graph** is a graph whose vertices can be divided into two sets so that every edge connects a vertex in one set to a vertex in the other set.

The problem of finding a shortest closed route that traverses every edge of a weighted graph at least once.

A vector written in component form as $\binom{x}{y}$, representing a translation of $x$ units horizontally and $y$ units vertically.

A graph where every pair of distinct vertices is joined by an edge.

A graph where every vertex can be reached from every other vertex by traveling along edges (possibly using several edges).

A path that starts and ends at the same vertex and does not pass through any vertex more than once.

The **degree** of a vertex is the number of edges meeting at that vertex (counting multiple edges separately).

A collection of vertices (nodes) connected by edges (links) that have a specific direction.

For $\mathbf{u}=\binom{u_1}{u_2}$ and $\mathbf{v}=\binom{v_1}{v_2}$, the dot product is $\mathbf{u}\cdot\mathbf{v}=u_1v_1+u_2v_2$.

A trail that uses every edge exactly once and ends at the starting vertex.

A trail that uses every edge exactly once but starts and ends at different vertices.

A Hamiltonian path that returns to its starting vertex.

A path that visits every vertex exactly once.

The magnitude of a vector A is the length of the vector A and is denoted by $|A|$.

For a vector $\mathbf{a}$, the vector $-\mathbf{a}$ has the same magnitude but the opposite direction.

A set of objects (called nodes or vertices) that are connected together.

Two vectors that point in the same or opposite direction. Equivalently, one is a scalar multiple of the other.

The vector from the origin $O$ to a point, written $\overrightarrow{OA}$.

The single vector that has the same effect as performing several vectors in sequence, for example $\mathbf{a}+\mathbf{b}$.

A vector of the form $k\mathbf{a}$, where $k$ is a number (scalar). It is parallel to $\mathbf{a}$ and has magnitude $|k|\,|\mathbf{a}|$.

A walk through a graph that does not repeat any edge.

A graph where edges have no direction, so if vertex $A$ is connected to vertex $B$, then $B$ is also connected to $A$.

A quantity with both magnitude (size) and direction, often represented by a directed line segment (an arrow).

A **weighted graph** is a graph in which every edge has an associated number (a weight), representing something like distance, time, cost, or risk.