chapter 2 graphs and networks

Question 1

graph consists of

Answer 1

nodes connected by arcs

Question 2

if a graph has a number associated with each edge

Answer 2

it is a weighted graph or network

Question 3

list of nodes (or vertices)

Answer 3

vertex set

Question 4

list of edges (or arcs)

Answer 4

edge set

Question 5

a subgraph

Answer 5

a part of the original graph

Question 6

degree of a node

Answer 6

number of edges incident to it

Question 7

a walk

Answer 7

a route through the graph along gedges from one vertex to the next

Question 8

a path

Answer 8

a walk in one no vertex is visited more than once

Question 9

a trail

Answer 9

a walk in which no edge is visited more than once

Question 10

a cycle

Answer 10

a walk in which the end vertexx is the same as the start vertex and no other vertex is visited more than once

Question 11

a connected graph

Answer 11

if all vertices have a path between them

Question 12

hamilitioian cycle

Answer 12

cycle that includes every vertex

Question 13

loop

Answer 13

edge that starts and finishes at same vertex

Question 14

simple graph

Answer 14

no loops and at most one edge connecting any pair of vertices

Question 15

digraph

Answer 15

graph with direction

Question 16

rulers handshake lemma

Answer 16

sum of degrees is twice the number of edges. so there’s an even amount of odd vertices

Question 17

tree

Answer 17

connected graph with no cycles

Question 18

spanning tree

Answer 18

subgraph including all vertices and a tree

Question 19

complete graph

Answer 19

each vertex is connected is directly connected to each of the other vertexes by a single edge

Question 20

isomorphic graph

Answer 20

same info but shown differently