Unit 4 - Introduction to Graphs

Question 1

Undirected Graphs

Answer 1

All the edges are bidirectional

Question 2

Vertices and Edges letters

Answer 2

Nodes or vertices (V)
Connection or lines edges (E)

Question 3

Finite graph

Answer 3

A graph with a finite number of nodes and edges

Question 4

Isolated node

Answer 4

Is a node without neighbors

Question 5

Simple graph

Answer 5

A graph that has no loops and it has no multiple edges

Question 6

Connected graph

Answer 6

A graph where there is a path between any two vertices

Question 7

Degree of a node

Answer 7

The number of edges starting from a node.
δ delta

Isolated nodes have 0 degree.
Loops count double and increase the node degree by 2.

Question 8

Handshaking lemma

Answer 8

In any finite, undirected and simple graph, the sum of the node degree is exactly twice the number of edges.

The sum of all node degrees of a graph is even (pari).

Question 9

Isomorphic

Answer 9

Two graphs which contain the same number of graph vertices connected in the same way.

Question 10

Regular graph

Answer 10

A graph in which every node has the same degree.
Generally the number of edges are 1/2ng
n = nodes
g = degree

Question 11

Planar graph

Answer 11

If it has an isomorphic representation that can be drawn in the plane without intersections.

Question 12

Euler polyhedral formula (planar graph)

Answer 12

v - e + f = 2

v = nodes
e = edges
f = number of faces

Question 13

Subgraph

Answer 13

is created by removing edges or nodes together with all edges ending in that node.

Question 14

Adiacent matrix

Answer 14

Is used for the compact representation of a graph.

Question 15

How is an adiacent matric of an undirected graph?

Answer 15

It is always symmetric, because an edge connect both one node to the other and vice versa.