D1 (Decision 1) 17 May 2013 Official Thread

for anyone to answer:-

Define: tree
define:spanning tree
define: bipartite graph

total 6 marks ! ill mark it

Reply 302

Anythingoo1

13

Original post by Westeros

I'm kinda' with you on that, they're both right at the bottom, definitely! I just hate finding the optimal solution etc on Linear Programming! I really hope I get an A in this exam!

P.S I'm glad someone understands my username
My Sun and Stars :cute:

yeah the optimals are a bit of a pain to do, especially when it's not an integer :frown:

same, if anything I need to learn all the definitions but there are so many! Same, good luck!

Haha, it's ok, I'm a bit of a Game of Thrones fan too, Moon of My World :h:

Reply 303

Original post by otrivine

for anyone to answer:-

Define: tree
define:spanning tree
define: bipartite graph

total 6 marks ! ill mark it

A tree is a connected graph with no cycles.
A spanning tree is a subgraph that contains all of the vertices of the graph and is also a tree.
A bipartite graph is a graph that has two sets of verticces in which arcs may only connect vertices in one set to vertices in the other set or vice versa.

Reply 304

Original post by Epic Flawless

A tree is a connected graph with no cycles.
A spanning tree is a subgraph that contains all of the vertices of the graph and is also a tree.
A bipartite graph is a graph that has two sets of verticces in which arcs may only connect vertices in one set to vertices in the other set or vice versa.

yes nicely said

my turn :smile:

Reply 305

Original post by otrivine

for anyone to answer:-

Define: tree
define:spanning tree
define: bipartite graph

total 6 marks ! ill mark it

A tree is a connected graph with no cycles

A spanning tree is a subgraph of say graph G, whose nodes and arcs all belong to G. It is also a tree.

A bipartite graph is a graph that consists of 2 sets of nodes, say sets A and B, where arcs connect nodes in different sets. E.g. an arc connects a node from set A to a node in set B. Nodes in the same set cannot be connected to each other.

Reply 306

Original post by otrivine

yes nicely said

my turn :smile:

Define:
Path
Alternating path
Matching

Btw, how long does it take for you to complete a paper?

Reply 307

Original post by TanishaBellum

A tree is a connected graph with no cycles

A spanning tree is a subgraph of say graph G, whose nodes and arcs all belong to G. It is also a tree.

A bipartite graph is a graph that consists of 2 sets of nodes, say sets A and B, where arcs connect nodes in different sets. E.g. an arc connects a node from set A to a node in set B. Nodes in the same set cannot be connected to each other.

Correct

Reply 308

A path is a finite sequence of arcs where the end vertex of an edge is the start vertex of the next edge. In a path no vertex can be visited more than once.

An alternating path is where you start from a node not in the initial matching then connect to a node in the matching and so on. So not in matching and in matching. Must start and end at nodes not in the initial matching. (poor explanation)

A matching is where some or all the nodes in set A are connected to nodes in set B.

Okay these were hard LOL sorry for butting in

Reply 309

Original post by otrivine

Correct

Btw does a spanning tree have to contain ALL the nodes from the tree? :confused:

Reply 310

Original post by TanishaBellum

A path is a finite sequence of arcs where the end vertex of an edge is the start vertex of the next edge. In a path no vertex can be visited more than once.

An alternating path is where you start from a node not in the initial matching then connect to a node in the matching and so on. So not in matching and in matching. Must start and end at nodes not in the initial matching. (poor explanation)

A matching is where some or all the nodes in set A are connected to nodes in set B.

Okay these were hard LOL sorry for butting in

The more succinct definition for an alternating path is:
An alternating path is a path from an unmatched vertex in one set to an unmatched vertex in the other set using arcs alternately not in/in the initial matching.

The definition for matching isn't quite right:
A matching is a one-to-one pairing between some of the vertices in one set to some of the vertices in the other set.

Reply 311

Original post by Epic Flawless

Define:
Path
Alternating path
Matching

Btw, how long does it take for you to complete a paper?

Path is a finite sequence of event such that the end vertex is the start vertex of the next but the vertex does not appear more than once.

Alternating path is a path in which the unmatched vertex of x matches to an unmatched vertex in Y that alternately uses arcs in/not in the matching.

mathcing is the 1-1 pairing of all or some of the elements of x to the elements in Y.

To be honest I finish exactly in 90minutes and u :smile:

Reply 312

Original post by Epic Flawless

Define:
Path
Alternating path
Matching

Btw, how long does it take for you to complete a paper?

I struggled with time A LOT but having done past papers i've become better at managing time. I usually have about 40-45 minutes for the last 2 questions and I spend around 30 minutes doing the first 3 questions which is long IMO. I want to speed up!

How about you?

Reply 313

Original post by TanishaBellum

Btw does a spanning tree have to contain ALL the nodes from the tree? :confused:

yes so its all the nodes included

Reply 314

Original post by TanishaBellum

Btw does a spanning tree have to contain ALL the nodes from the tree? :confused:

It does indeed. You defined a subgraph, apart from the last bit about the tree?

Reply 315

Original post by otrivine

Path is a finite sequence of event such that the end vertex is the start vertex of the next but the vertex does not appear more than once.

Alternating path is a path in which the unmatched vertex of x matches to an unmatched vertex in Y that alternately uses arcs in/not in the matching.

mathcing is the 1-1 pairing of all or some of the elements of x to the elements in Y.

To be honest I finish exactly in 90minutes and u :smile:

I finish in about 50-55 mins before checking which makes me quite nervous because I normally finish in about 40-45 mins for non-Decision papers. :/

Reply 316

Original post by Epic Flawless

I finish in about 50-55 mins before checking which makes me quite nervous because I normally finish in about 40-45 mins for non-Decision papers. :/

I literally do a question and check it and then never come back to it so less time consuming.

are my defintions correct?

Reply 317

Original post by Epic Flawless

I finish in about 50-55 mins before checking which makes me quite nervous because I normally finish in about 40-45 mins for non-Decision papers. :/

Thats really quick! How do you finish the paper so quickly!?

Reply 318

Original post by otrivine

I literally do a question and check it and then never come back to it so less time consuming.

are my defintions correct?

Of course, they are! :biggrin:

I'm worried about making a mistake in the exam, because I know that would be deadly in decision since the following questions always stem from the first (e.g inspection, CPA, Dijkstra's). Especially because I was making silly mistakes in the mechanics exam, but fortunately, I had enough time to check, idenify and correct them.

Reply 319