Graphs terminology

Question 1

Undirected graph

Answer 1

A non-empty graph where the edges do not have a specified direction

Question 2

Directed graph (digraph)

Answer 2

A non-empty graph where the edges have a specified direction

Question 3

Source

Answer 3

Digraph - where an edge starts

Question 4

Sink

Answer 4

Digraph - where an edge ends

Question 5

Subgraph

Answer 5

A subset of the vertices and edges in a graph

Question 6

undirected -> directed

Answer 6

Assing a directionality, then give each edge an additional symetric edge

Question 7

directed -> undirected

Answer 7

Remove the directionality of each edge, then remove duplicate edges

Question 8

Weighted graph

Answer 8

Graph with real-valued weights assigned to the edges - stored instead of bools in adjacency list/matrix

Question 9

Adjacency (undirected)

Answer 9

Two nodes are adjacent if they are connected by an edge

Question 10

Adjacency (directed)

Answer 10

Node A is adjacent to node B if there is an edge from B to A.
Generally, a node is adjacent to another node if the first node has an inbound edge from the second node

Question 11

Connected

Answer 11

(undirected) A path exists from every node to every other node

Question 12

Weakly connected

Answer 12

(dircted) A path exists from every node to every other node ignoring directionality

Question 13

Strongly connected

Answer 13

(directed) A path exists from every node to every other node taking directionality into account

Question 14

Complete

Answer 14

Every node has an edge to every other node

Question 15

Clique

Answer 15

A complete subgraph containing two or more nodes

Question 16

Maximum clique

Answer 16

The largest clique of a given graph

Question 17

Maximal clique

Answer 17

A clique that is not a part of a larger clique

Question 18

Acyclic

Answer 18

A graph that does not contain any cycles (non-self loops)

Question 19

In-degree

Answer 19

(directed) The number of incoming edges to a node

Question 20

Out-degree

Answer 20

(directed) The number of outgoing edges from a node

Question 21

Reflexive

Answer 21

All nodes have self loops

Question 22

Irreflexive

Answer 22

No nodes have self loops

Question 23

Symmetric

Answer 23

(directed) All edges are reciprocated

Question 24

Anti-symmetric

Answer 24

(directed) No edge is reciprocated (does not exclude self loops)

Question 25

Transitive

Answer 25

If a path exists between two nodes, there must be an edge directly linking them

Question 26

path

Answer 26

The route(s) from one node to another

Question 27

Subpath

Answer 27

A section of a path

Question 28

Path length (weighted)

Answer 28

The combined/total weight/cost of traversing a given path

Question 29

Settled

Answer 29

Refers to Dijsktra's: The shortest path to this node from the starting node has been found

Question 30

Frontier

Answer 30

Refers to Dijsktra's: Just discovered this node, working on confirming the shortest path

Question 31

Unexplored

Answer 31

Refers to Dijsktra's: The algorithm has not seen this node yet