Dtjytyk

Multiplicative persistence

Is this toilet slogan correct usage of the English language?

How to implement a feedback to keep the DC gain at zero for this conceptual passive filter?

Count the occurrence of each unique word in the file

Why does the Sun have different day lengths, but not the gas giants?

Is there a name for this algorithm to calculate the concentration of a mixture of two solutions containing the same solute?

Does the expansion of the universe explain why the universe doesn't collapse?

Fear of getting stuck on one programming language / technology that is not used in my country

Is it possible to have a strip of cold climate in the middle of a planet?

Biological Blimps: Propulsion

Why is it that I can sometimes guess the next note?

Is it safe to use olive oil to clean the ear wax?

Melting point of aspirin, contradicting sources

Did arcade monitors have same pixel aspect ratio as TV sets?

Yosemite Fire Rings - What to Expect?

I am looking for the correct translation of love for the phrase "in this sign love"

How should I respond when I lied about my education and the company finds out through background check?

Non-trope happy ending?

Is the U.S. Code copyrighted by the Government?

The IT department bottlenecks progress. How should I handle this?

Loading commands from file

Freedom of speech and where it applies

When a Cleric spontaneously casts a Cure Light Wounds spell, will a Pearl of Power recover the original spell or Cure Light Wounds?

GraphicsGrid with a Label for each Column and Row

Geodesic is a path

Shortest acyclical path between two nodes, negative weights allowedProve that in a tree, a path is a hamilton path iff it is an euler pathProve that G has a vertex adjacent to all other verticesMax length of a path in a connected graphShortest path between two points on graph?Connected Linear Graph not Path-ConnectedProve that a sum of degrees in a path between two vertices is smaller than $3n$Is determining a geodesic on a riemannian manifold a limit case of the shortest path problem in a graph?Prove that the shortest path between two points in a Delaunay triangulation minimizes angle at each step.Show that if $G$ is connected then $L(G)$ is connected

0

$begingroup$

Let G a graph (connected) and the walk $T = (u, x_1, dots , x_k, v)$ a geodesic (walk with the shortest distance) between the vertex $u$ and $v$. Show that:
1. $T$ is a path.
2. If $i,j in {1, dots, k }$ and $i leq j$ then the walk $(x_i, T, x_j)$ is a geodesic between $x_i$ and $x_j$.

In (1) I have the idea to led a contradiction:
Proof: Suppose that $T$ is not a path, i.e. there's at least one vertex with more than one occurrence. Since $G$ is connected then there's a path between $u$ and $v$. So, let $T'$ a path between $u$ and $v$, since $T$ is a path then it has the shortest distance between these two vertex. So $T'$ is geodesic and $T$ is not. Contradiction.

In (2) I must to assume that the vertex are not adjacent, but since then, what?

graph-theory

share|cite|improve this question

asked Mar 14 at 0:36

Eric ToporekEric Toporek

969

$endgroup$

add a comment | 

0

$begingroup$

Let G a graph (connected) and the walk $T = (u, x_1, dots , x_k, v)$ a geodesic (walk with the shortest distance) between the vertex $u$ and $v$. Show that:
1. $T$ is a path.
2. If $i,j in {1, dots, k }$ and $i leq j$ then the walk $(x_i, T, x_j)$ is a geodesic between $x_i$ and $x_j$.

In (1) I have the idea to led a contradiction:
Proof: Suppose that $T$ is not a path, i.e. there's at least one vertex with more than one occurrence. Since $G$ is connected then there's a path between $u$ and $v$. So, let $T'$ a path between $u$ and $v$, since $T$ is a path then it has the shortest distance between these two vertex. So $T'$ is geodesic and $T$ is not. Contradiction.

In (2) I must to assume that the vertex are not adjacent, but since then, what?

graph-theory

share|cite|improve this question

asked Mar 14 at 0:36

Eric ToporekEric Toporek

969

$endgroup$

add a comment | 

$begingroup$

Let G a graph (connected) and the walk $T = (u, x_1, dots , x_k, v)$ a geodesic (walk with the shortest distance) between the vertex $u$ and $v$. Show that:
1. $T$ is a path.
2. If $i,j in {1, dots, k }$ and $i leq j$ then the walk $(x_i, T, x_j)$ is a geodesic between $x_i$ and $x_j$.

In (1) I have the idea to led a contradiction:
Proof: Suppose that $T$ is not a path, i.e. there's at least one vertex with more than one occurrence. Since $G$ is connected then there's a path between $u$ and $v$. So, let $T'$ a path between $u$ and $v$, since $T$ is a path then it has the shortest distance between these two vertex. So $T'$ is geodesic and $T$ is not. Contradiction.

In (2) I must to assume that the vertex are not adjacent, but since then, what?

graph-theory

share|cite|improve this question

asked Mar 14 at 0:36

Eric ToporekEric Toporek

969

$endgroup$

share|cite|improve this question

asked Mar 14 at 0:36

Eric ToporekEric Toporek

969

share|cite|improve this question

asked Mar 14 at 0:36

Eric ToporekEric Toporek

969

asked Mar 14 at 0:36

Eric ToporekEric Toporek

969

asked Mar 14 at 0:36

Eric ToporekEric Toporek

969

1 Answer
1

active

oldest

votes

1

$begingroup$

For (1), if you remove the first and last occurrence of the repeated vertex in $T$ you obtain a shorter walk Than $T$ which is a contradiction.

For (2), if $(x_i, T, x_j)$ is not geodesic then there is a shorter walk between $x_i$ and $x_j$ which means that $T$ is not geodesic because you can get shorter walk between $u$ and $v$ by replacing $(x_i, T, x_j)$ in $T$ the shorter walk between $x_i$ and $x_j$ which is contradiction

share|cite|improve this answer

answered Mar 14 at 2:06

hbmhbm

1,027166

$endgroup$

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3147403%2fgeodesic-is-a-path%23new-answer', 'question_page');
}
);

Post as a guest

Name

Email

Required, but never shown

1

$begingroup$

For (1), if you remove the first and last occurrence of the repeated vertex in $T$ you obtain a shorter walk Than $T$ which is a contradiction.

For (2), if $(x_i, T, x_j)$ is not geodesic then there is a shorter walk between $x_i$ and $x_j$ which means that $T$ is not geodesic because you can get shorter walk between $u$ and $v$ by replacing $(x_i, T, x_j)$ in $T$ the shorter walk between $x_i$ and $x_j$ which is contradiction

share|cite|improve this answer

answered Mar 14 at 2:06

hbmhbm

1,027166

$endgroup$

add a comment | 

1

$begingroup$

For (1), if you remove the first and last occurrence of the repeated vertex in $T$ you obtain a shorter walk Than $T$ which is a contradiction.

For (2), if $(x_i, T, x_j)$ is not geodesic then there is a shorter walk between $x_i$ and $x_j$ which means that $T$ is not geodesic because you can get shorter walk between $u$ and $v$ by replacing $(x_i, T, x_j)$ in $T$ the shorter walk between $x_i$ and $x_j$ which is contradiction

share|cite|improve this answer

answered Mar 14 at 2:06

hbmhbm

1,027166

$endgroup$

add a comment | 

$begingroup$

For (1), if you remove the first and last occurrence of the repeated vertex in $T$ you obtain a shorter walk Than $T$ which is a contradiction.

For (2), if $(x_i, T, x_j)$ is not geodesic then there is a shorter walk between $x_i$ and $x_j$ which means that $T$ is not geodesic because you can get shorter walk between $u$ and $v$ by replacing $(x_i, T, x_j)$ in $T$ the shorter walk between $x_i$ and $x_j$ which is contradiction

share|cite|improve this answer

answered Mar 14 at 2:06

hbmhbm

1,027166

$endgroup$

share|cite|improve this answer

answered Mar 14 at 2:06

hbmhbm

1,027166

answered Mar 14 at 2:06

hbmhbm

1,027166

answered Mar 14 at 2:06

hbmhbm

1,027166